Some questions of Erdős and Graham on numbers of the form ∑𝑔_{𝑛}/2^{𝑔_{𝑛}}

Abstract

Erdös in 1975 and Erdös and Graham in 1980 raised several questions concerning representing numbers as series of the form <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Sigma Subscript n equals 1 Superscript normal infinity Baseline g Subscript n slash 2 Superscript g Super Subscript n"> <mml:semantics> <mml:mrow> <mml:msubsup> <mml:mi mathvariant="normal">Σ<!-- Σ --></mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi mathvariant="normal">∞<!-- ∞ --></mml:mi> </mml:msubsup> <mml:mspace width="thickmathspace" /> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\Sigma _{n = 1}^\infty \;{g_n}/{2^{{g_n}}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. For example, does the equation <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartFraction n Over 2 Superscript n Baseline EndFraction equals sigma-summation Underscript k equals 1 Overscript upper T Endscripts StartFraction g Subscript k Baseline Over 2 Superscript g Super Subscript k Superscript Baseline EndFraction comma upper T greater-than 1 comma"> <mml:semantics> <mml:mrow> <mml:mfrac> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> </mml:mfrac> <mml:mo>=</mml:mo> <mml:munderover> <mml:mo movablelimits="false">∑<!-- ∑ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mi>T</mml:mi> </mml:munderover> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> </mml:mfrac> <mml:mo>,</mml:mo> <mml:mspace width="1em" /> <mml:mi>T</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\frac {n}{{{2^n}}} = \sum \limits _{k = 1}^T {\frac {{{g_k}}}{{{2^{{g_k}}}}},\quad T &gt; 1} ,</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula> have a solution for infinitely many <italic>n</italic> ? The answer to this question is affirmative; in fact, we conjecture that the above equation is solvable for every <italic>n</italic>. This conjecture is based on a more general conjecture, namely that the algorithm <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a Subscript n plus 1 Baseline equals 2 left-parenthesis a Subscript n Baseline mod n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo lspace="thickmathspace" rspace="thickmathspace">mod</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{a_{n + 1}} = 2({a_n}\bmod n)</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula> with initial condition <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a Subscript m Baseline element-of bold upper Z"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">Z</mml:mi> </mml:mrow> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{a_m} \in {\mathbf {Z}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> always eventually terminates at zero. This, in turn, is based on an examination of how the "greedy algorithm" can be used to represent numbers in the form <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma-summation g Subscript n Baseline slash 2 Superscript g Super Subscript n"> <mml:semantics> <mml:mrow> <mml:mo>∑<!-- ∑ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\sum {{g_n}/{2^{{g_n}}}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The analysis of this, reformulated as a "base change" algorithm, proves surprising. Some numbers have a unique representation, as above, others have uncountably many. Also, from this analysis we observe that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="sigma-summation g Subscript n Baseline slash 2 Superscript g Super Subscript n"> <mml:semantics> <mml:mrow> <mml:mo>∑<!-- ∑ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\sum {{g_n}/{2^{{g_n}}}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is irrational if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="limit sup Underscript n Endscripts left-parenthesis left-parenthesis g Subscript n plus 1 Baseline minus g Subscript n Baseline right-parenthesis slash log left-parenthesis g Subscript n plus 1 Baseline right-parenthesis right-parenthesis equals normal infinity"> <mml:semantics> <mml:mrow> <mml:mo movablelimits="true" form="prefix">lim</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:munder> <mml:mo movablelimits="true" form="prefix">sup</mml:mo> <mml:mi>n</mml:mi> </mml:munder> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>−<!-- − --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>g</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi mathvariant="normal">∞<!-- ∞ --></mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\lim {\sup _n}(({g_{n + 1}} - {g_n})/\log ({g_{n + 1}})) = \infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and conjecture that this is best possible.

Locations

• Mathematics of Computation - View - PDF