7
$\begingroup$

This question is related to Gromov's theorem in that it is about the growth rate with respect to some set of generators of $\mathbb Z$. Gromov's Theorem, along with the Bass-Guivarc'h formula, tells us that for any finite symmetric set of generators $S$ of $\mathbb Z$, if we let $$B_n = \{x \in \mathbb Z : \exists k \leq n, s_1, \ldots, s_k \in S \text{ such that }n = s_1 + \cdots + s_k\}$$ and $c(n) = \left|B_n\right|$, then $c(n) \in \Theta(n)$ since $\operatorname{rank} \mathbb Z = 1$.

Computational evidence leads me to expect that there is a stronger condition on $c(n)$: I conjecture that $c(n)$ is necessarily linear for large enough $n$, that is, that there are some integers $N, a, b$ such that for all $n \geq N$, we have $c(n) = an + b$.

Is this conjecture true or not? Can anyone think of a proof either way?

EDIT: Computing the growth rates induced from various generating sets makes me think that in fact we have $c(n)$ linear for all $n$ such that $\{-\max S, \ldots, -1, 0, 1, \ldots, \max S\} \subseteq B_{n-1}$, or equivalently for all $n > \max d^{-1}[\{-\max S, \ldots, 0, \ldots, \max S\}]$, where $d : \mathbb Z \to \mathbb N$ is given by $d(k) = \min\{n \in \mathbb N : k \in B_n\}$; this gives a very precise bound on where the linearity must start, and in most cases this bound is actually sharp.

EDIT 2: Allow me to describe some of my observations. The Mathematica code I used is provided below.

  • $S = \pm \{4, 7\}$. Here are some plots which tell about the behavior of the $B_n$ and of $c(n)$: Behavior of $B_n$ and $c(n)$ for $S = \pm \{4, 7\}$ The upper plot, with all the dots, shows the nonnegative elements of each $B_n$ for $n = 0, 1, \ldots, 10$. ($B_n$ is always symmetric, so we do not need to show both sides.) Note that $\max S = 7$, and observe from this plot that $B_n$ contains $\{-7, -6, \ldots, 6, 7\}$ for $n \geq 5$. Now, the lower-left plot is just $c(n)$ vs. $n$, and the lower-right plot is of the differences $c(n) - c(n - 1)$. Gromov's Theorem says that $c(n) \in \Theta(n)$, and indeed the lower-left plot shows that $c(n)$ looks linear. The lower-right plot strongly suggests that $c(n)$ is exactly linear for $n > 5$, with formula determined to be $c(n) = 14n - 9$. Looking back at the various $B_n$, one may observe that the right "edge" of each $B_n$ is exactly the same for $n \geq 5$, which is itself close to a proof that $c(n)$ is linear past this point.

  • $S = \pm \{1, 2, 9\}$. Here are the plots: Behavior of $B_n$ and $c(n)$ for $S = \pm \{1, 2, 9\}$ Here again my conjectures seem to be confirmed: the lower-right plot suggests that $c(n)$ is eventually linear with slope 18, and furthermore $\max S = 9$, and we see from the upper plot that for all $n \geq 3$, $\{-9, -8, \ldots, 8, 9\} \subseteq B_n$, and from the lower-right plot again that $c(n)$ is linear on $n \geq 3$. (It in fact seems that the bound on where linearity begins is sharp exactly when $1 \not\in S$, and needs to be shifted left by one when $1 \in S$.)

Here is the code. gens specifies the positive portion of the generators you wish to use (e.g. if gens = {2, 3}, then $S = \{-3, -2, 2, 3\}$), while iters and countsiters just say how much data to show: iters is the number of balls $B_n$ to display in the first plot, and countsiters is the number of ball-sizes $c(n)$ to display in the lower plots.

(* input parameters *)
gens := {6, 7}
iters := 10
countsiters := 20

(* computation *)
MinkowskiSum[lst__] := DeleteDuplicates[Total /@ Tuples[{lst}]]
MinkowskiProduct[lst__] := 
 DeleteDuplicates[Apply[#1 #2 &, Tuples[{lst}], {1}]]
Clear[b]
allgens := MinkowskiProduct[gens, {-1, 0, 1}]
b[-1] := {}
b[0] := {0}
b[n_] := b[n] = MinkowskiSum[b[n - 1], allgens]
c[n_] := Length[b[n]]

(* plots *)
ListPlot[Table[{#, -n} & /@ Select[b[n], # >= 0 &], {n, 0, iters}], 
 AspectRatio -> 3*iters/(Max[b[iters]] - Min[b[iters]]), 
 GridLines -> {Range[0, iters Max[allgens]], Range[-iters, 0]}, 
 Ticks -> {Range[0, iters Max[allgens], 5], Range[-iters, 0]}, 
 ImageSize -> Full]
{DiscretePlot[c[n], {n, 0, countsiters}, ImageSize -> Large], 
 DiscretePlot[c[n] - c[n - 1], {n, 0, countsiters}, 
  ImageSize -> Large]}
$\endgroup$
8
  • $\begingroup$ Is this related to the Frobenius coin problem? I would expect that what you'd actually is a growth rate like c(n) = an + b(n), where a = max |s_i| and b(n) is a (bounded) periodic or at least eventually-periodic function. $\endgroup$
    – anomaly
    Feb 18, 2017 at 0:24
  • $\begingroup$ It might be related to the coin problem (I would need to think more about it to see a precise relationship), but what you say should be expected must be amended: usually (or at least with all the generating sets I examined) the linear coefficient $a$ will not be $\max S$ -- usually it will be a lot higher. Also, every single generating set I have looked at so far has induced an exactly-linear (for large enough $n$) growth rate, with no periodicity to be seen. I would be surprised to see any periodicity, but I don't know that there is none! $\endgroup$
    – feralin
    Feb 18, 2017 at 0:28
  • $\begingroup$ Right: It's too late to edit the comment above, but it should clearly be something like 1/max(|S|) rather than max(|S|) itself. The greedy algorithm plus the result that the coin problem is solvable for sufficiently large n gives you that bound. $\endgroup$
    – anomaly
    Feb 18, 2017 at 0:57
  • $\begingroup$ Wouldn't that make the coefficient even smaller? My observations have been that $a >> \max S$, but $a > 1 / \max S$ tells us nothing, since always $a \geq 2$. $\endgroup$
    – feralin
    Feb 18, 2017 at 0:58
  • $\begingroup$ Yes, I read your original statement. That's probably a clue that I should go to bed rather than trying to fix the comments above. :) $\endgroup$
    – anomaly
    Feb 18, 2017 at 1:01

1 Answer 1

2
$\begingroup$

Let $m=\max(S).$ Then $c(n)$ does eventually have growth rate $2m.$ In other words, there is an $N$ with $c(n+1)=c(n)+2m$ for $n \gt N.$ This most easily shown by considering each congruence class $\bmod m$ separately. I will think of the members of $S$ as positive and allow sums $x=\pm s_1 \pm s_2 \pm \cdots.$

Define $f(x)=f(-x)$ to be the least $k$ so that $x \in B_k$ and call a sum $s_1 \pm \cdots \pm s_k=x$ good if $k=f(x).$ The main insight is that for "large" $x>0$ , all good sums contain one or more terms $+ m$ so that $f(x)=f(x-m)+1$ and each $B_n$ contains just one $x \gt 0$ with $x \equiv r \bmod m$ and $x \notin B_{n-1}.$

Call $x>0$ normal if every good sum for $x$ uses a $+ m$ and exceptional otherwise. (we could say that $-x$ is normal or exceptional as well but we don't need that.) In a good sum, no value $s \notin \{{\pm m\}}$ is used more than $m$ times (we could replace $m$ values of $\pm s$ with $s$ values of $ \pm m$.) As a consequence, there are only finitely many exceptional $x.$

For $x \gt m$ normal we have $f(x)=f(x-m)+1$ and also $f(-x)=f(-x+m)+1.$ Let $X$ be the largest exceptional integer. I'm sure that $X \gt m$ but set $X=m$ if this is not the case. Also, let $N$ be large enough that $\{{-X,\cdots,X\}} \subseteq B_N.$ I will show that for every $n \gt N$ and $0 \le r \lt m$ there is exactly one positive $x$ with $x \equiv r \bmod m$ and $f(x)=n.$ Then $c(n)=c(n-1)+2m$ as desired.

Consider the positive integers $r,r+m,r+2m,\cdots.$ There is a smallest one, say $y=qm+r$ with $f(y)\ge n.$ But $y$ is normal so $f(y)=f(y-m)+1 \le n.$ So $f(y)=f(y-m)+1=n.$ Similarly, $f(y+m)=f(y)+1=n+1$, $f(y+2m)+f(y+m)+1=n+2$ etc. Hence, as desired, $y$ is the unique positive member of its congruence class in $B_n$ and we are done.

LATER

Since the thought process for this proof was requested, let me sketch an alternate proof I was aiming for. I got bogged down in the details so ended with what is above. I think I can get the clearer proof now though I'll be less formal (but I'll try positive and negative at the same time). Call $x \in \mathbb{N}$ weird if there is a good sum for $x$ which uses neither $m$ nor $-m.$ (Note for sticklers: $0$ is weird.) First let me give a proof that there are only finitely many weird numbers. Then I will show that the $f$ values for $\cdots -2m+r,-m+r,r,m+r,2m+r,\cdots$ are determined by the $f$ values for the weird members of this congruence class. Finally I will show that this gives the result.

Observe that a good sum stays good if we delete one (or more ) terms. A good sum for an weird number can't use more that $m-1$ terms: Consider the partial sums $0,\pm s_1, \pm s_1 \pm s_2$ etc. If there are more than $m$ of them then some two are congruent mod $m$ and we can get from the first one to the second more quickly by using a few $\pm m$'s instead.

Associate with each $x$ a good sum for $x$ (There might be several, just pick one.) If that sum uses neither $+m$ nor $-m$ then $x$ is weird. If it uses $+m$ $j>0$ times then $y=x-jm$ is weird. Let $f(y)=k,$ then $f(x)=f(x-jm)+j=f(y)+j=k+j.$ We have a chain of decreasing $f$ values from $x$, $f(x)=k+j,f(x-m)=k+j-1,\cdots,f(x-jm)=f(y)=k$ ending at $y$ which is weird (the case of using $-m$ is similar.) Note that the chain stays entirely in the congruence class of $x.$

Each congruence class has at least one weird member. Consider the largest and smallest weird members of that class (which might be the same number.) If the largest weird member is $y$ with $f(y)=k$ then we know about all larger members of that congruence class: $f(y+jm)=k+j$ Similarly if $y'$ is the smallest weird member of the class with $f(y')=k'$ then we know for all the smaller members of the class $f(y'-\ell m)=k'+\ell.$

This doesn't tell us explicitly what $f(x)$ is for the members of the congruence class which fall between $k'$ and $k.$ But we don't care. If $n$ is large enough then all those members have an $f$ number less than $n$ and when we pass from $B_{n-1}$ to $B_{n}$ we just add two new members of the congruence class $qm+r:$ $f(y+(n-k)m)=f(y'-(n-k')m)=n.$ If $n$ is really large then this is true for all the congruence classes and then $c(n)=c(n-1)+2m.$ DONE

$\endgroup$
4
  • $\begingroup$ Thanks for answering! I haven't looked through your proof yet, but I will take a look soon and then accept or comment. $\endgroup$
    – feralin
    Feb 19, 2017 at 19:04
  • $\begingroup$ A quick note: I think you should define $x = \pm s_1 \pm s_2 \cdots$, since otherwise (for example) for every $s \in S$ we would have $f(s) = 1$ and $f(-s) > 1$. $\endgroup$
    – feralin
    Feb 19, 2017 at 19:20
  • $\begingroup$ Wow, very nice proof! This is much better than the proof I was working on. Question: in the last paragraph is $y$ normal since $f(y) \geq n > N$, but all the exceptional numbers are in $B_N$, so their $f$-values are $\leq N$? Also, if you remember can you say how you came up with this proof? $\endgroup$
    – feralin
    Feb 19, 2017 at 19:42
  • $\begingroup$ @feralin yes, I'll fix it if I edit. $\endgroup$ Feb 19, 2017 at 23:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .