17
$\begingroup$

Let $S$ be the set of polynomials defined as follows: $0$ is in $S$, and if $p$ is in $S$, then $p + 1$ is in $S$ and $x \cdot p$ is in $S$, so that $S$ "grows" in generations: $g(0)=\{0\}$, $g(1)=\{1\}$, $g(2)=\{2,x\}$, $g(3)=\{3,2x,x+1,x^2\}$, and so on, with $|g(n)|=2^{n-1}$. Let $S^*$ be the set obtained from $S$ by substituting $r=\sqrt{2}$ for $x$ and keeping only the first appearance of each duplicate. Successive generations $G(n)$ now begin with $\{0\}$, $\{1\}$, $\{2,r\}$, $\{3,2r,r+1\}$, with $|G(n)|$ starting with $1,1,2,3,4,7,11,18,29,...$; i.e., Lucas numbers beginning at the 4th term, and checked for 30 generations. Can someone prove that $|G(n)|=L(n-1)$ for $n \geq 4$?

$\endgroup$
16
  • 4
    $\begingroup$ Welcome to MO! I have edited your post to use LaTeX instead of ascii (which was conflicting with MO's markup syntax). But I think something is missing in your definition of $S$, as multiplying $0$ with $x$ only gives back $0$. Maybe it is also allowed to add $1$? $\endgroup$ Jan 29, 2015 at 17:52
  • 3
    $\begingroup$ Responding to D.Z., calling it r suggests the more general problem of using an arbitrary algebraic number (such as the golden ratio). Then the main question is this: Is $G(n)$ linearly recurrent. $\endgroup$ Jan 29, 2015 at 20:35
  • 1
    $\begingroup$ I think the main step here is the following observation (for $r = \sqrt 2$): Every element $q$ of $\mathbb{N} + \mathbb{N}r$ can be written uniquely as a finite sum $r^{a_1} + r^{a_2} + ... + r^{a_k}$ for nonnegative integers $a_1,a_2,...,a_k$ satisfying $a_1 < a_2 < ... < a_k$. (Indeed, just write the integral and the $r$-integral parts of $q$ in binary.) We denote the nonnegative integer $k + a_k$ as the energy of $q$ (where $a_k := 0$ if $k = 0$). Now if I am not mistaken, then an inductive argument shows that ... $\endgroup$ Jan 29, 2015 at 20:42
  • 1
    $\begingroup$ ... for every $n \in \mathbb{N}$, every element of $\mathbb{N} + \mathbb{N} r$ having energy $n$ belongs to $G(n)$, and that every element of $G(n)$ must have energy $n$ (these inductions need to happen in lockstep). As a consequence, it easily follows that $G(n)$ is the set of all elements of $\mathbb{N} + \mathbb{N} r$ having energy $n$. $\endgroup$ Jan 29, 2015 at 20:43
  • 1
    $\begingroup$ The induction relies on the lemma that for every $q \in \mathbb{N} + \mathbb{N}r$, the energy of $q+1$ is $\leq$ to (the energy of $q$) plus $1$. This is rather annoying to formalize, but I am fairly sure that the "follow your nose" proof goes through. (The idea is: Write $q$ as $r^{a_1}+r^{a_2}+...+r^{a_k}$ as above. Let $u$ be the smallest even integer which does not belong to $\left\{a_1,a_2,...,a_k\right\}$. Then, $q=r^{b_1}+r^{b_2}+...+r^{b_l}$, where $\left(b_1,b_2,...,b_l\right)$ is the result of removing the entries $0,2,...,u-2$ from the sequence $\left(a_1,a_2,...,a_k\right)$ and ... $\endgroup$ Jan 29, 2015 at 20:58

2 Answers 2

15
$\begingroup$

For a number of the form $a + b\sqrt{2}$ with nonnegative integers $a$ and $b$, define its length to be the minimal number of steps needed to obtain it from zero, where the allowed steps are $x \mapsto x+1$ and $x \mapsto \sqrt{2}x$. Then the problem asks to count the numbers of given length.

Now it should be easy to show the following by induction:

  • If $a$ is odd, then the last step must be $x \mapsto x+1$ (this is clear).
  • If $a$ is even, then the last step can be taken to be $x \mapsto \sqrt{2}x$, unless $a + b\sqrt{2} = 2$.

EDIT: Here is a proof. Let $\ell(x)$ be the length of $x$.

Lemma. Write $x = a_0 + a_1 \sqrt{2} + a_2 \sqrt{2}^2 + \ldots + a_k \sqrt{2}^k$ with $a_j \in \{0,1\}$ and $a_k = 1$.

If $x > \sqrt{2}$, then $\ell(x) = k + \#\{j : a_j = 1\} - (1 - a_{k-1})$.

Proof. Write $\ell'(x) = k + \#\{j : a_j = 1\} - (1 - a_{k-1})$. The proof is by induction on $x$ (the set of all possible $x$ has the order type of the natural numbers). We have $\ell(1 + \sqrt{2}) = 3 = \ell'(1 + \sqrt{2})$. So assume $x \ge 2$. If $a_0 = 1$, then $\ell(x) = \ell(x-1) + 1 = \ell'(x-1) + 1 = \ell'(x)$ (this needs that $0 \neq k-1$, so that changing $a_0$ from 1 to 0 does not affect $a_{k-1}$). If $a_0 = 0$, then $\ell(x) \le \ell(x/\sqrt{2}) + 1 = \ell'(x/\sqrt{2}) + 1 = \ell'(x)$, so we need to show that $\ell'(x-1) \ge \ell(x/\sqrt{2}) = \ell'(x) - 1$. We can assume $x > 2$, since the claim of the lemma holds for $x = 2$. The rational part (denoted $a$ above) of $x$ must be at least 2 (it must be positive, otherwise $x-1$ is not of the required form, and even since $a_0 = 0$). Then in $x-1$, either $k$ stays the same and we have the same or a larger number of 1's among the $a_j$, which shows $\ell'(x-1) \ge \ell'(x) - 1$. (Note that $a_{k-1}$ could change from 1 to 0.) Or else $k$ gets smaller; then $a = 2^m$ and $k = 2m$ in $x$, and $a = 2^m-1$, $k \le 2m-1$ in $x-1$. So we reduce $k$ by at least 1, but increase the number of 1's by $m-1$. Note also that $a_{k-1}$ can only change from 1 to 0 if $k$ goes down by 2. So $\ell'(x-1) \ge \ell'(x) + m - 2 \ge \ell'(x) - 1$ as before. $\Box$

Assuming this, we can arrange our numbers $a + b\sqrt{2}$ into a rooted tree with zero at the root and where an odd number (meaning odd $a$) has only one (even) child, whereas an even number has two children, one odd and one even. There are two exceptions: the odd node $1$ has the two children $2$ and $\sqrt{2}$, and the even node $\sqrt{2}$ has only one child $1 + \sqrt{2}$. So the $n$th level of the tree, for $n \ge 3$, consists of the $n$th level of the usual Fibonacci tree (think of the rabbits) (with root $1$), together with the ($n-2$)nd level of the Fibonacci tree (with root $1 + \sqrt{2}$). This gives $F_n + F_{n-2} = L_{n-1}$ for the number of nodes at distance $n$ from the root (the root has level $1$).

REMARK. Replacing $\sqrt{2}$ by $2$ gives a somewhat simpler problem that leads to the Fibonacci tree (starting at $1$) and gives Fibonacci numbers. The golden ratio $(1+\sqrt{5})/2$ gives the sequence $(1,2,3,5,8, 12, 18, 25, 35, 51,\ldots)$ (starting at generation 1), apparently satisfying $a_n = a_{n-1}+a_{n-3}$ for $n \ge 12$. [Previously, I claimed that one gets Fibonacci numbers, but this is wrong.] If we take any number $r > 1$ instead of $\sqrt{2}$, then I would expect that for any $x \in R = {\mathbb Z}_{\ge 0}[r]$ that is divisible by $r$ and sufficiently large, the shortest path to zero is via division by $r$. For any other $x$, one is forced to go via $x-1$. So in the relevant tree, if we are at a sufficiently high level, nodes $x$ such that $x+1$ is divisible by $r$ in the semiring $R$ have one child $rx$ and the other nodes have two children $x+1$ and $rx$. I would expect this to lead to a linear recurrence with constant coefficients, but since we are dealing with a semiring and not with a ring (where we could consider the quotient by the ideal generated by $r$), this is not clear to me.

$\endgroup$
3
  • $\begingroup$ I'm stuck somewhere in the middle of the proof of Michael's Lemma. See where $\ell'(x-1) \ge \ell'(x)-1$? It appears that this is intended to imply $\ell'(x) \le \ell(x)$, so that, with what's proved earlier, we'll have $\ell'(x) = \ell(x)$. However, $\ell'(6-1) = 5 = \ell(5)$. What'm I missing? $\endgroup$ Aug 24, 2015 at 20:48
  • $\begingroup$ Oops. I left something out in the above Comment. Use this one instead. See where $\ell'(x-1) \ge \ell'(x)-1$? It appears that this is intended to imply $\ell'(x) \le \ell(x)$, so that, with what's proved earlier, we'll have $\ell'(x) = \ell(x)$. The desired $\ell'(x) \le \ell(x)$ would follow if $1+\ell'(x-1 \le \ell(x)$, but that's not available; e.g., $\ell'(6-1) = 5 = \ell(5)$. What'm I missing? $\endgroup$ Aug 24, 2015 at 21:08
  • $\begingroup$ $\ell'(6-1) = \ell'(5) = 5 \ge 5 - 1 = \ell'(6) - 1$, so where is the problem? (Also, $\ell(6) = 5 = \ell'(6)$ and $\ell(5) = 5 = \ell'(5)$.) Note that $\ell(x) = 1 + \min\{\ell(x/\sqrt{2}), \ell(x-1)\} = 1 + \min\{\ell'(x/\sqrt{2}), \ell'(x-1)\}$, the second equality by the inductive assumption. If $\ell'(x-1) \ge \ell'(x/\sqrt{2}) = \ell'(x) - 1$, then the first term gives the minimum, and $\ell(x) = \ell'(x)$. $\endgroup$ Aug 25, 2015 at 10:39
3
$\begingroup$

I seem to be a bit short of a proof. But here is a much refined conjecture which might lead to a proof. I construct sets $H(3),H(4),\cdots$ where $H(n)$ has $L_{n-1}$ elements and then conjecture, with support, that $H(n)=G(n)$ for all $n.$

Just to fix notation, the Fibonacci numbers starting with $F_0$ are $0,1,1,2,3,5,\cdots.$ Call a binary sequence good if it has no two consecutive $0$'s. There are $F_{n+2}$ good binary sequences of length $n$. Of these , $F_{n}$ start with $0$ and $F_{n+1}$ start with $1.$ The Lucas numbers starting with $L_1$ are $1,3,4,7,11,18,\cdots$ with $L_n=F_{n-1}+F_{n+1}=2F_{n-1}+F_n.$

We want to show that, starting with $n=3,$ The set $G(n)$ has size $L_{n-1}.$ I will attempt to do this (but not totally succeed) by associating with each element of $G(n)$ a code consisting of a letter , $A,B$ or $C$, followed by a good binary sequence of length $n-2$, with the added condition that we must start $A0,B0$ or $C1.$ The code will give a unique recipe for each element starting from $H(3)=G(3).$ To be clear I will call the sets I construct $H(3),H(4),\cdots$ and conjecture that they are the same as $G(3),G(4),\cdots$

Here are the cases $n=3,4,5$ with the codes. Skip this example (for now) if you want the recipe first . Read it now if you want to guess the (simple) recipe.

$H(3)=G(3)=\{\sqrt{2}+1,3,2\sqrt{2}\}$ with codes $\{A0,B0,C1\}$

$H(4)=G(4)=\{2+\sqrt{2},3\sqrt{2},2\sqrt{2}+1,4 \}$ with codes $\{A01,B01,C10,C11\}$

$H(5)=G(5)=\{3+\sqrt{2},2+2\sqrt{2},3\sqrt{2}+1,6,4+\sqrt{2},5,4\sqrt{2} \}$ with codes $\{A010,A011,B010,B011,C101,C110,C111\}$

Recipe given $p$ in $H(n)$, put $q=p\sqrt{2}$ into $H(n+1)$ and append $1$ to the end of the the code for $p$ in order to get the code for $q.$ If the code for $p$ ends in a $1$ then also put $q'=p+1$ into $H(n+1)$ and append $0$ to the end of the the code for $p$ in order to get the code for $q'.$

Certainly, if $H(n)=G(n)$ then everything placed in $H(n+1)$ either belongs in $G(n+1)$ or, perhaps, is already in $G(m)$ for some $m \le n.$

CONJECTURE H(n+1)=G(n+1).

I will discuss this a bit more at the end.


Observe that $H(n)$ has $F_{n-2}$ elements whose code starts $A0$, another $F_{n-2}$ which start $B0$ and $F_{n-1}$ whose code starts with $C1.$ In all, this gives

$$2F_{n-2}+F_{n-1}=L_{n-1}$$

elements in $H(n).$

The fact that we never get the same thing twice in building $H(n)$ follows from this observation (an easy induction): Recall that $L_{n-1}=L_{n-3}+L_{n-2}.$

  • There are $L_{n-3}$ elements $a+b\sqrt{2} \in H(n)$ with $a$ odd and these are the ones whose code ends in $0.$

  • There are $L_{n-2}$ elements $a+b\sqrt{2} \in H(n)$ with $a$ even and these are the ones whose code ends in $1.$


Further Discussion define the weight ( or length) of a number $p=a+b\sqrt{2}$ to be $w(p)=m$ if $p \in G(m).$ Here $a,b \ge 0$ and we will ignore $0,1,\sqrt{2}$ and $2.$ Then for $a=2j+1$ we must have $w(a+b\sqrt{2})=w(2j+b\sqrt{2})+1.$ For $a=2j+2$ we have that $w(a+b\sqrt{2})$ is either $w(b+(j+1)\sqrt{2})+1$ or $w(2j+1+b\sqrt{2})+1$ whichever is smaller. Although this is quite rapid, it is not immediate when $w(p) \lt w(q),$ even for $p,q \in \mathbb{Z}.$

The conjecture amounts to saying that we always have $$w(b+(j+1)\sqrt{2}) \le w(2j+1+b\sqrt{2}).$$ I actually conjecture that this is a strong inequality. For small cases the discrepancy is $1$ or $2.$ However $w(32+8\sqrt{2})=11$ while $w(15+32\sqrt{2})=15.$ For $b=33$ and $b=34$ it turns out that $w(b+8\sqrt{2})=12$ while $w(15+b\sqrt{2})=16.$

For $p=7+11\sqrt{2}$ it turns out that $w(p)=12$, $w(p\pm 1)=w(p\pm \sqrt{2})=11$ and $w(p \pm(1 \pm \sqrt{2})=10.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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