Fibonacci Numbers Everywhere?

September 19, 2011

Let a_n be a sequence with values in \mathbb{N} and let

\alpha(n):=\min\{m\in\mathbb{N}: n|a_m\}

be the first index m such that n divides a_m whenever it exists (otherwise it stays undefined). Next define a sequence by the following recurrence:



a_{x+2}:= 1+\sum_{n:\alpha(n)\leq x} \varphi(n) \left\lfloor\frac{x}{\alpha(n)}\right\rfloor

for 0\leq x\in\mathbb{N }. Here, \varphi denotes Euler’s totient function. Note that the sum is extended over all n with \alpha(n)\leq x. The values of \alphaare thus defined. Moreover, the sum is finite.

What is a_n? As it turns out and as you might have guessed from the title a_n is the well-known Fibonacci series.

Computational example. Assume we knew that the a_n were the Fibonacci numbers for 1\leq i\leq 5. Then  a_7 = 1+\sum_{n\in\{1, 2, 3, 5\}}\varphi(n)\left\lfloor\frac{x}{\alpha(n)}\right\rfloor where the sum is extended over all divisors of a_1, \ldots , a_5 (i.e. the divisors of 1, 1, 2, 3, 5). Thus

a_7 = 1+1 \left\lfloor\frac{5}{1}\right\rfloor+1 \left\lfloor\frac{5}{3}\right\rfloor+2\left\lfloor\frac{5}{4}\right\rfloor+4 \left\lfloor\frac{5}{5}\right\rfloor = 13.

How does one prove that the a_n are indeed the Fibonacci numbers? Actually, there is a nice and elementary double counting proof for this and even after scribbling it down I must confess that for me the Fibonacci numbers here somehow pop out of nowhere.

Polymath5 – A somewhat surprising observation

April 5, 2011

In this post, Kevin O’Bryant has considered “least nonzero digit”-type examples \lambda_{m, S}. Encouraged by his remark that there are only very few possibilities, i.e. feasible sets S, for each modulus m I did a complete enumeration up to modulus 200. The goal was (and still is) to find a slowly growing example possibly beating \mu_{3} the current record holder (please read my last post for more information).

Much to my surprise there are certain “magic” numbers with comparatively many feasible sets S. What follows is a table (modulus m: number of sets S) for those m with more than 4 sets:

(39: 24)
(87: 560)
(95: 3.360)
(111: 5.280)
(119: 42.772)
(135: 5.940)
(145: 11.440)
(159: 64.064)
(183: 13.728)

All other m < 200 have 4 or less feasible sets.

For example, there is no set S for m=105. This can be seen as follows: Logarithmic discrepancy of \lambda_{105} implies \sum_{i=1}^{d-1} \lambda_{105}(i)=0 for d|105. Since 3,5,7|105 complete multiplicativity implies \lambda_{105}(2)=\lambda_{105}(3)=\lambda_{105}(5)=-1. Now 45^2\equiv 30 \mod 105 and again since \lambda_{105} is completely multiplicative 1=\lambda_{105}(30)=\lambda_{105}(2)\lambda_{105}(3)\lambda_{105}(5)=-1 produces a contradiction.

What makes these number “special”? Why is there this huge jump from 4 to “many”? Is this just one more “random” number theoretic artifact or can we understand this by considering how the m-examples are constructed from the d|m-examples?

I do not know the answers, but let me close with something I do know. In my last post I gave a proof that any \lambda_{m,S} that grows slower than \mu_3 must have m>729. Subsequent computer searches have increased that bound to 1000.

Polymath5 – A collection of results concerning the completely multiplicative case

March 23, 2011

In this post I have collected results of the fifth Polymath project on the Erdös discrepancy problem. With hundreds and maybe even thousands of posts I have decided to restrict this to the (maybe) simplest non-trivial special case, namely completely multiplicative functions with values in {\{\pm 1\}}. That has some justification since there are results reducing the problem to the completely multiplicative case (albeit with values in {S_1}). Furthermore my focus is on elementary examples related to the problem and how far one can get with textbook methods. It that sense this can be seen as a beginner’s guide with the quoted results being nothing more than exercises. I have arranged the results within the following sections

  • Statement of the problem
  • Examples related to the problem
  • Necessary conditions for bounded discrepancy
  • Discrepancy results

What fascinates me about the problem is that it can be stated without much technicalities and that a solution seems to be within reach due to recent results in number theory.

Discrepancy Problem. Find or prove the non-existence of a function {f:\mathbb{N}\rightarrow\{\pm 1\}} with the following properties:

  • {f} is completely multiplicative, i.e. {f(m n)=f(m) f(n) } for all {m,n\in\mathbb{N}}.
  • {f} has bounded partial sums (bounded discrepancy), i.e. there is a {C>0} such that {\left|\sum_{n\leq x}f(n)\right|\leq C} for all {x\in\mathbb{R}}.

Let me fix some notation before I present examples related to the above question. In the following {f} denotes a completely multiplicative function with values in {\{\pm 1\}}, {p,q} denote primes and {s=\sigma + i t} is a complex number with real part {\sigma} and imaginary part {t}.

Examples related to the problem.

  • {f(n)=1} for all {n\in\mathbb{N}} is completely multiplicative and has unbounded discrepancy {\sum_{n\leq x}1=\lfloor x\rfloor}.
  • Liouville function {\lambda(p):=-1} for all primes {p}.
  • Dirichlet characters of modulus {k} are completely multiplicative with values in {\{0\}\cup\{e^{2 \pi i n / k}:1\leq n \leq k\}}. Since Dirichlet characters assume the value {0} they are strictly speaking not in the focus of this post. However, they can be used to construct {\{\pm 1\}}-valued examples (cf. the next example) and they play a central role in the discussions.
  • The functions \displaystyle \mu_p(q):=\left\{ {(\frac{q}{p}) \textnormal{ if } q\not= p} \atop -1 {\textnormal{ if } q=p}\right. and \displaystyle \lambda_p(q):=\left\{ {(\frac{q}{p}) \textnormal{ if } q\not= p} \atop 1 {\textnormal{ if } q=p}\right.with {(\frac{q}{p})} being the quadratic Dirichlet character mod {p} (Legendre symbol) and {p} an odd prime.
  • To generalize the last example fix {m \in \mathbb{N}} and a set {S\subseteq \{1,\ldots, m-1\}}. Define {\lambda_{m,S}(n):=1} if the last non-zero digit of {n} in its {m}-ary representation is in {S}. In all other cases {\lambda_{m,A}(n):=-1}. Immediately from the definition we find \displaystyle \lambda_{m,S}(n+l)=\lambda_{m,S}(n) if {\textnormal{ord}_m l>\textnormal{ord}_m n}. To not obtain unbounded discrepancy it is necessary that {\sum_{i=1}^{m/d-1}\lambda_{m,S}(i)=0} for {1<d|m}. Moreover, we find {\sum_{i=1}^{n}\lambda_{m,S}(i)=\sum_{j=0}^l \sum_{i=1}^{d_j}\lambda_{m,S}(i) } which implies logarithmic growth. Since {\lambda_{m,S}} is completely multiplicative we have {\lambda_{m,S}(n)=1 } if n is a quadratic residue mod {m}, implying {\lambda_{p,S}=\lambda_p} for {p} an odd prime. We construct some {\lambda_{m,S}} for small composite {m}:
    • For {m=9} we have for the quadratic residues {\{1,4,7\} \subseteq S} and thus depending on whether we include {3} either {\lambda_{9,\{1,3,4,7\}}=\lambda_3} or {\lambda_{9,\{1,4,6,7\}}=\mu_3}.
    • For {m=15} we get {\{1,4,6,9,10\} \subseteq S}. Since {\sum_{i=1}^4 \lambda_{15,S}(i)=0} for all {S} we cannot include {2} and {3}. Because {10} is included this forces {\lambda_{15,S}(5)=-1} for all {S}. Now using complete multiplicativity and {\sum_{i=1}^{14} \lambda_{15,S}(i)=0} we get the four cases: {S_{15,\{1,4,6,9,10,11,14\}}}, {S_{15,\{1,4,6,7,9,10,11\}}}, {S_{15,\{1,4,6,9,10,13,14\}}} and {S_{15,\{1,4,6,7,9,10,13\}}}.
    • For {m=21} we have that {9^2\equiv 18 \mod 21}. Thus {1=\lambda_{21,S}(18)=\lambda_{21,S}(2)}. Since {3|21} we have {\sum_{i=1}^2\lambda_{21,S}(i)=0}, a contradiction.

Necessary conditions for bounded discrepancy.

  • If {f} has bounded partial sums, then the Dirichlet series {\sum_{n\leq x} \frac{f(n)}{n^s}} converges for {\sigma>0}. Proof idea: Integration by parts.
  • If {f} has bounded partial sums, then {\sum_{p\leq x} \frac{f(p)}{p}=A+O\left(\frac{1}{\log{x}}\right)}. Proof idea: One first establishes {\sum_{p\leq x} \frac{f(p)\log{p}}{p}=O(1)} like in the proof of Dirichlet’s theorem on primes in arithmetic progressions. This estimate is then used in the textbook proof on the growth of {\sum_ {p\leq x} \frac{1}{p}}.
  • If {f} has bounded partial sums, then for infinitely many primes {p} one has {f(p)=1} and for infinitely many primes {q} one has {f(q)=-1}. Proof idea: Otherwise one would get a contradiction to the standard result on the growth of {\sum_{p\leq x} \frac{1}{p}}.
  • With not so elementary methods one can prove results ‘in the spirit of’: Let {f:\mathbb{N}\rightarrow S_1} have bounded partial sums and let {\chi} be a non-principal Dirichlet character. Then {\sum_{p}\frac{|1-f(p)\overline{\chi(p)}|}{p}=\infty}. Here more serious number theory kicks in and this is probably where most are currently heading to.

Discrepancy results.

  • Computer experiments (no link found) show that there are {f} with {\left|\sum_{n\leq x}f(n)\right|\leq 2} for all {x\leq 246}. No such sequence exists for {x=247}. There is no traditional proof of this, not even for {x=\infty}.
  • Liouville’s function does not have bounded partial sums since its Dirichlet series equals {\frac{\zeta(2 s)}{\zeta(s)}} and thus has a singularity at {s=\frac{1}{2}}.Alternatively one can proceed as in the proof of Dirichlet’s theorem on primes in arithmetic progressions and apply Dirichlet’s hyperbola method to {A(x):= \sum_{n\leq x}\frac{1*\lambda(n)}{\sqrt{n}}} ultimately showing that under the assumption of bounded partial sums {A(x)} grows like {\sqrt{x}}. This is a contradiction since {A(x)} grows logarithmically. Showing that the discrepancy of the Liouville function is {O(n^{1/2+\varepsilon})} for all {\varepsilon>0} is equivalent to solving the Riemann hypothesis.
  • For primitive Dirichlet characters {\chi} mod {k} one has {\max_{n\leq x}\left|\sum_{i\leq n}\chi(i) \right|\geq \frac{\sqrt{k}}{2\pi}}. Proof idea: Apply partial summation to the associated Gauss sum {G(1,\chi):=\sum_{1\leq m\leq k} \chi(m) e^{2 \pi i m /k}} and use {|G(1,\chi)|^2=k}.
  • We have {\mu_3(n) = \lambda_{9,\{1,4,6,7\}}(n)} and  \displaystyle \left|\sum_{i=1}^n\mu_3(i)\right|\leq\log_9(8n+1) with equality holding only for {n=\frac{9^m-1}{8}} and {m\in\mathbb{N}}.
  • {\mu_3} is optimal in the following sense: \displaystyle \limsup_{x\rightarrow\infty}\frac{\left|\sum_{n\leq x}\mu_p(n)\right|}{\log{x}}\geq \frac{1}{2 \log{3}} with equality holding only for {p=3}. Proof idea: One constructs a sequence {x_i} such that {\lim_{x_i\rightarrow\infty}\frac{\left|\sum_{n\leq x_i}\mu_p(n)\right|}{\log{x_i}}\geq \frac{M_p-m_p}{2\log{p}}} with {M_p:=\max_{1\leq n< p}\sum_{1\leq i\leq n} (\frac{i}{p})} and {m_p:=\min_{1\leq n< p}\sum_{1\leq i\leq n} (\frac{i}{p})}. With the lower bound for the discrepancy of primitive Dirichlet characters one can eliminate all but finitely many cases. These can then be checked by computer. A similar argument shows that the sums of {\lambda_p} grow faster than {\mu_3}.
  • Computer experiments so far did not find a {\lambda_{m, S}} that grows slower than {\mu_3}. For a given {\lambda_{m,S}} let {M_{m,S}:=\max_{1\leq n< m}\left|\sum_{1\leq i\leq n} \lambda_{m,S}(i)\right|}. Then {m=39} with {S=} \displaystyle \{1,3,4,9,10,12,13,14,16,19,22,25,27,29,30,31,34,35,36\} is the largest {m} such that there is an {S} with {M_{m,S}=2}. Proof idea: Do a computer search among all completely multiplicative discrepancy 2 functions with domain {\{1,\ldots,m-1\}} ({m} must be less than 247). A {\lambda_{m, S}} beating {\mu_3} thus has at least {M_{m,S}=3} and thus {\frac{1}{\log 9}>\frac{3}{\log m}} implying {m>729}.

EDP and some first steps in number theory

February 12, 2011

Last year I have spent some time to think about the Erdös Discrepancy Problem (EDP). My interest was sparked by Tim Gower’s Polymath project and two comments of Terence Tao (1, 2) on the special case of completely multiplicative functions. Let me state this version of EDP.

Problem. Prove or disprove the existence of a function {f:\mathbb{N}\rightarrow\{\pm 1\}} with the following properties

  • {f} is completely multiplicative, i.e. {f(m n)=f(m) f(n) } for all {m,n\in\mathbb{N}}.
  • {f} has bounded partial sums, i.e. there is a {C>0} such that {\left|\sum_{n\leq x}f(n)\right|\leq C} for all {x\in\mathbb{R}}.

In his comments Terence Tao describes how one can use ideas of Dirichlet’s proof (of the theorem on primes in arithmetic progressions) to get first an elementary proof of the unboundedness of the summatory Liouville function and second a necessary condition for unbounded discrepancy using properties of {\sum_{p\leq  x}f(p)}. While the ‘positivity’ part is straight forward I had some trouble to fully digest the complex analysis part at the end of his second comment (bounded discrepancy implies {\sum_{p\leq  x} f(p)=o\left(x/ \log x\right)}). However, all this can be achieved with textbook arguments and I took this as an opportunity to learn some (analytic) number theory. In what follows I elaborate some ideas on the analytic number theory approach and (in an upcoming post) on the positivity approach (Dirichlet’s idea).

Analytic Method. To show where we can apply complex analysis let me first repeat a standard argument. Define { \psi_f(x):=\sum_{n\leq  x}f(n)\Lambda(n) } with {\Lambda} being the von Mangoldt function. Plugging in the definition yields

\displaystyle  \psi_f(x)=\sum_{p\leq  x}\sum_{\alpha=1 \atop p^\alpha\leq x} f(p^\alpha)\log p=\sum_{p\leq  x}\log p\sum_{\alpha=1}^{\left\lfloor\log_p x\right\rfloor} f(p)^\alpha.

Separating primes with {f(p)=1} from primes with {f(p)=-1} we find (using {\{x\}:=x-\lfloor  x\rfloor})

\displaystyle   \begin{array}{rcl}  \psi_f(x) & = & \sum_{p\leq x\atop  f(p)=1}\log p\left\lfloor\log_p x\right\rfloor - \sum_{p\leq x,  \left\lfloor\log_p x\right\rfloor \textnormal{ odd}\atop f(p)=-1}\log  p\\ & = & \log x \sum_{p\leq x\atop f(p)=1}1 - \sum_{p\leq  x\atop f(p)=1}\log p\left\{\log_p x\right\} \\ & & \hspace{1cm}-  \sum_{p\leq x, \left\lfloor\log_p x\right\rfloor \textnormal{ odd}\atop  f(p)=-1}\log p. \end{array}

Setting {f(n)=1} for all {n} we find that {\psi(x)= \pi(x)\log  x-\sum_{p\leq x}\log p\left\{\log_p x\right\}} and since {\pi(x)\frac{\log x}{x}=\frac{\psi(x)}{x}+o(1)} we find for all {f}

\displaystyle  \begin{array}{rcl}  0\leq\sum_{2<p\leq x\atop  f(p)=1}\log p\left\{\log_p x\right\} & \leq & \sum_{2<p\leq  x}\log p\left\{\log_p x\right\}\\ & = & -\log 2\left\{\log_2  x\right\}+o(x). \end{array}

Defining {\pi_{f,1}(x):=\sum_{p\leq x\atop  f(p)=1}1} and {\vartheta_{f,-1}(x):=-\sum_{p\leq  x\atop f(p)=-1}\log p} we arrive at the


\displaystyle   \psi_f(x)=\pi_{f,1}(x)\log x +\sum_{1\leq i \textnormal{ odd}}  \left(\vartheta_{f,-1}(x^\frac{1}{i})-  \vartheta_{f,-1}(x^\frac{1}{i+1})\right)+o(x)

The above argument indicates how to proceed. Using analytic number theory similar to the proof of the prime number theorem (PNT) one gets information on {\psi_f(x)} for general {f}. It might even be possible to prove that {f} having bounded partial sums implies {\psi_f(x)=o(x)}, although I have not yet checked the details. If true, we would get a nice analog to the PNT in the (still maybe empty) case of bounded partial sums.

Conjecture. If {f} has bounded partial sums, then

\displaystyle  \pi_{f,1}(x)\frac{\log x}{x} =-\frac{1}{x}\sum_{1\leq i  \textnormal{ odd}} \left(\vartheta_{f,-1}(x^\frac{1}{i})-  \vartheta_{f,-1}(x^\frac{1}{i+1})\right)+o(1).

Fürstenberg’s proof on the infinity of primes revisited

August 6, 2010

Warning to teaching staff: summing infinite sequences of positive (>0) integers is difficult, but possible. For example \sum_{n=0}^\infty n \cdot n!=0 is not a mistake and students must get full marks. Let me show you why.

A couple of months ago I was hoping to ‘cheat’ a proof of the Erdös discrepancy conjecture by using a variant of an idea of Fürstenberg’s proof on the infinitude of primes. Remember, Fürstenberg considered the integers with a new topology. Its open sets  are \{a+n b: n\in\mathbb{Z}\} for a\in\mathbb{Z} and b>0.

This topology is metrizable. There are a couple of hand-waving arguments how this metric could look like. However, as far as I am aware of, there is so far no neat description in the literature. A couple of days ago, R. Lovas and I. Mezö have published a fairly straightforward proof that d(n,m)=\|n-m\| with \|n\|:=\frac{1}{\max\left\{k\in\mathbb{N}_{>0}:1|n,2|n,\ldots,k|n\right\}} induces the above topology.

Since \|n!\|\leq\frac{1}{n} the sequence (n!)_{n\in\mathbb{N}} converges to 0 in this topology. The partial sums of \sum_{n=0}^\infty n \cdot n! satisfy \sum_{k=0}^{n-1} k \cdot k!=n! and thus \sum_{n=0}^\infty n \cdot n!=0.

R. Lovas and I. Mezö have collected more such observations in their note. What they did not mention explicitly, but what I consider interesting is that with the above metric, the integers become an ultrametric space. Without loss of generality we assume \|m\|\leq\|n\|. Then 1,2,\ldots,\frac{1}{\|n\|} are all divisors of m and n and thus they are divisors of m+n. Therefore \|m+n\|\leq \|n\|=\max\{\|m\|,\|n\|\}. The strong triangle inequality now follows d(m,n)=\|m-l+l-n\|\leq \max\{d(m,l),d(l,n)\}.

The Plan II

July 26, 2010

Its Polymath time. My resources, especially time and most importantly skill, are limited and therefore I have to restrict myself a little. Let me just sketch where I set the boundaries, what I want to try and what a possible (successful) outcome might look like. Some acquaintance with Tim Gowers’s proof of Roth’s theorem and its (hoped for) connection to EDP is necessary.

What is the idea?

Let me first collect some observations:

  • ‘Translation’ acts as a group on APs and is periodic on APs with common difference.
  • ROI starts with some representation of the translation group in terms of rank one projections using exponentials.
  • An elementary formula from Fourier Analysis describing the interaction of translation and exponentials is used to express the exponentials in terms of Fourier coefficients of some characteristic function and its translates.
  • The result is an ‘efficient’ representation, i.e. it allows to deduce unbounded discrepancy.

Translation as described above lives on the domain of the Fourier coefficients. We do not lose information if we consider it for the corresponding Fourier series. On all reasonable spaces translations form a strongly continuous (semi-) group of linear operators.  For periodic strongly continuous groups we have representations of the group. If we work with rotation groups on L^p(\Gamma) with p>1 we even have a tensorial representation in terms of exponentials. By the way, if we choose our space carefully, exponentials are at least approximative eigenvectors of translations (rotations).

The idea now is to get information on discrepancy on  \mathbb{Z} (the domain of the Fourier coefficients) by studying ROI on various spaces of Fourier series, like L^p(\Gamma) or L^1(\mathbb{R})\cap L^1(\mathbb{R}) .

If I am not able to translate the ROI idea to the infinite section directly I will also try to use the so called ‘Complex Inversion Formula’, expressing the integral over the group in terms of some inverse Laplace transform. This can be seen as an infinite dimensional version of Perron’s formula. However that would be a ‘last try’ since it is not connected to Polymath anymore.

What is the goal?

The result I am aiming for looks roughly as follows:

Let X be a Banach (or better a Hilbert) space and let T be a strongly continuous (maybe only semi-)group of linear operators (translations, rotations, periodic?) with generator  (A,D(A)). If the resolvent (\lambda- A)^{-1} satisfies some conditions (including norm estimates) then ‘something’ has unbounded ‘discrepancy’.

That sounds incredibly naive, since Tim Gowers’s proof needed some clever estimates and preyed upon cancellations for different common differences  d. My hope is to hide these technicalities in an estimate on the resolvent. Such estimates  like e.g. in the Hille-Yosida theorem are usually harder to obtain than to state. That is good news.

So far, that would be the first part. In a way this is just translating the main idea of the proof into some other language. The hard part would then be to apply the general theorem to other situations (maybe even EDP). Here the resolvent has to be estimated and technicalities enter. However, I do not want to think that far ahead.

The Plan

July 23, 2010

So far that was a hot summer. With all written and oral exams finished and with bearable temperatures returning I plan to spend some free time to think about the Erdös Discrepancy Conjecture. Is it wise to post this plan? I think so. It puts some pressure on me and this is good.

The idea is that we have probably not made maximal use of Tim Gowers’s proof of Roth’s theorem.  Behind all the numbers and estimates there could be some abstract/infinitary content. If this is the case, then it might be easier to generalize or at least to spot the limits of the method.

Intuition or wishful thinking? Maybe the later, but I want to know for sure.