MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $f:\mathbb{N}\to\mathbb{N}$ be defined in the following recursive way: for any $n$ in $\mathbb{N}$, $f(n)$ is the least natural number different from all $f(k)$ and $f(k)+k+1$ with $k<n$ (for instance, $f(0)=0$, $f(1)=2$, $f(2)=3$, $f(3)=5$). Is it possible to define this function in the language of Presburger arithmetic (the same question about the function defined as above, but with $f(k)+k$ instead of $f(k)+k+1$)?

share|cite|improve this question
If we call $g$ the second function you defined then $g(k+1)=f(k)+1$ for all $k$. So $g$ is definable in Presburger arithmetic if and only if $f$ is. – Ramiro de la Vega Nov 21 '12 at 14:32
The first 20 values of $f(n)$ match , which has the growth rate $n(1+\sqrt 5)/2+O(1)$, and hence is not definable in Presburger arithmetic. – Emil Jeřábek Nov 21 '12 at 15:07
Not only the first 20 values of $f(n)$ match the corresponding ones at - all values given there are the same as the corresponding function values. A proof of the general statement is thus desirable. – Dimiter Skordev Nov 21 '12 at 19:10
up vote 4 down vote accepted

$\let\fii\varphi\let\ol\overline$Andreas has already answered the original question, however it was raised in the comments whether $f$ coincides with the sequence in $$\tag{$*$}f(n)=\lfloor n\fii+\fii^{-1}\rfloor=\lfloor(n+1)\fii\rfloor-1,$$ where $\fii=(1+\sqrt5)/2$ is the golden ratio, so let me argue that this is indeed the case.

Every integer $n\ge0$ can be written as $n=\ol a:=\sum_{i=2}^\infty a_iF_i$, where $F_i$ is the $i$th Fibonacci number, and $a=(a_i)_{i\ge2}$ is a sequence such that $a_i\in\{0,1\}$, $a_i=0$ for all but finitely many $i$, and no two consecutive elements of $a$ are $1$. (We can find find such a representation recursively by choosing the largest $i$ such that $F_i\le n$, and combining it with a representation of $n-F_i$. This is known as the Zeckendorf expansion of $n$.) Let $A$ denote the set of all such sequences $a$. It is easy to see that if $i$ is the largest index of a nonzero element of $a\in A$, then $\ol a< F_{i+1}$; it follows that $\ol a< \ol b$ iff $a< b$ in the lexicographic order. In particular, the representation is unique.

Define $f'\colon\mathbb N\to\mathbb N$ by $f'(\ol a)=\ol{a0}$, where for $u\in\{0,1\}$, $au$ denotes the concatenation of $u$ and $a$: $(au)_{i+1}=a_i$, $(au)_2=u$. In other words, $f'(\ol a)=\sum_ia_iF_{i+1}$. Clearly, $f'$ is an increasing function. Moreover, $$f'(\ol a)+\ol a+1=\sum_ia_i(F_i+F_{i+1})+1=\sum_ia_iF_{i+2}+F_2=\ol{a01}.$$ It follows that $\mathbb N$ is the disjoint union of $\{f'(k):k\in\mathbb N\}$ and $\{f'(k)+k+1:k\in\mathbb N\}$. Then it is easy to show $$f(n)=f'(n)$$ by induction on $n=\ol a$: indeed, $a0$ is the lexicographically least sequence in $A$ excluded from $\{b0,b01:b< a\}$.

Since $F_i=\bigl(\fii^i-(-\fii)^{-i}\bigr)/\sqrt5$, we have $$f(n)-\fii n=\sum_{i:a_i=1}(F_{i+1}-\fii F_i)=\sum_{i:a_i=1}(-\fii)^{-i}\frac{\fii^{-1}+\fii}{\sqrt5}=\sum_{i:a_i=1}(-\fii)^{-i}.$$ Thus, \begin{align*} f(n)-\fii n&< \sum_{\substack{i\ge2\\\\i\text{ even}}}\fii^{-i}=\frac{\fii^{-2}}{1-\fii^{-2}}=\fii^{-1},\\\\ f(n)-\fii n&>-\sum_{\substack{i\ge2\\\\i\text{ odd}}}\fii^{-i}=-\frac{\fii^{-3}}{1-\fii^{-2}}=-\fii^{-2}=\fii^{-1}-1, \end{align*} which shows $(*)$.

share|cite|improve this answer

Suppose, toward a contradiction, that $f$ is definable in Presburger arithmetic. By quantifier elimination for Presburger arithmetic, there must be a constant $M$ such that, on each congruence class modulo $M$, $f$ is an affine function $f(n)=an+b$ except for finitely many $n$'s, and the coefficient $a$ of the linear term is rational. Furthermore, since $f$ is clearly monotone, these coefficients $a$ must be the same for all of the congruence classes.

Now consider (approximately) what happens when we compute, using the inductive definition, $f(n)$ for a large $n$, large enough so that the constant terms $b$ are negligible. $f(n)$ is defined as the first number different from the $n$ numbers $f(k)$ and the $n$ other numbers $f(k)+k+1$ for all $k$ in the range $0\leq k<n$. Notice first that "other" is literally correct; no number appears in both sets of $n$. How many of these $2n$ numbers are relevant in the sense that they are below $f(n)$ and thus really matter in the calculation of $f(n)$? One answer to this question is $f(n)$, since $f(n)$ is the first number above all of them; remember that this is roughly $an$. Another answer is that all of the first set of $n$ (the values of previous $f(k)$'s) are relevant, but in the second set, whose largest elements are roughly $an+n$, only those below roughly $an$ are relevant. Altogether, we have roughly $n+(an/(an+n))=n(2a+1)/(a+1)$ relevant numbers, and $f(n)$, being the first number different from these, is roughly of this size. Thus, we must have $a=(2a+1)/(a+1)$. This means that $a$ must equal the golden ratio. But we know, from quantifier elimination, that $a$ must be rational. This contradiction shows that $f$ cannot be definable in Presburger arithmetic.

share|cite|improve this answer
The argument I gave for the growth rate, approximately linear with the golden ratio as coefficient, was done under the assumption of Presburger definability, an assumption that I showed is false. Nevertheless, the growth rate looks plausible even without the false assumption, and its plausibility is certainly increased by Emil's comment (which arrived while I was typing my answer). – Andreas Blass Nov 21 '12 at 15:17
Let $\alpha=\liminf_nf(n)/n$, $\beta=\limsup_nf(n)/n$. Clearly $1\le\alpha\le\beta\le2$, and I believe your argument gives $\beta\le1+\beta/(1+\alpha)$ and $\alpha\ge1+\alpha/(1+\beta)$. This implies $1+\beta\le\alpha\beta\le1+\alpha$, thus $\alpha=\beta=\phi$, i.e., $f(n)\sim\phi n$. – Emil Jeřábek Nov 21 '12 at 20:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.