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_1:=1

and

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.


Upcoming Courses

July 28, 2011

Starting in Oktober I will give Mathematics for Engineers II which is basically Ordinary Differential Equations and Real Analysis (of functions with several variables). The course will be in german. Since the material is standard I won’t bother translating it and bringing it here.

The other new course will be Metamathematics. I have not yet decided on the exact content.


Treating Markets Mechanically – An Example

April 27, 2011

The aim of this post is to provide the transition from time-independence to time-dependence within a simple economic model for further reference.

For that purpose we consider a single consumer-worker. This agent obeys a time constraint on labour L and free time F

L + F = 1.

We introduce a utility function U as

U = C^\alpha F^{1-\alpha}

for a given 0< \alpha<1. There is a budget constraint W given as price p times consumption C equals wage rate w  times labour L.

p C = w L.

The agent now maximizes U such that p C + w F = w. Let us solve that. Lagrange equations yield

-\frac{\partial U}{\partial C} = \lambda \frac{\partial W}{\partial C}

and

-\frac{\partial U}{\partial F} = \lambda \frac{\partial W}{\partial F}

with constraint

W = p C + w F -w = 0.

Thus

\frac{p}{w}=\frac{\alpha C^{\alpha-1} F^{1-\alpha}}{(1-\alpha) C^\alpha F^{-\alpha}}=\frac{\alpha F}{(1-\alpha) C}.

Solving that for C and plugging it into the budget constraint yields

\frac{\alpha}{(1-\alpha)}w F+w F -w =0.

Solving this for F and again using the budget constraint shows that

F=1-\alpha

and

C=\alpha\frac{w}{p}

solves the maximization problem. So far there is no time evolution. To introduce such a dynamics we mimic mechanics and set C=C(p,\dot{p}). Demand is a function of price and its derivative. For economists the \dot{p} comes from nowhere. Especially since it is not obvious at all how to define the derivative of a price evolution. For now it has to suffice that eventually we shall understand the derivative in a distributional sense and until then we treat it as a formal parameter.

The time-dependent utility function for the consumer-worker

U = C^\alpha F^{1-\alpha}r^t

for a discount rate 0<r\leq1. The agent now maximizes \int_0^T U d t under the constraint p C + w F = w.

We make the following assumption due to S. Smale (for excess demand):

\dot{p}=C \textnormal{ and }\dot{w}=L.

Euler-Lagrange equations yield

\frac{d}{d t}\frac{\partial U}{\partial C} = \lambda \frac{\partial W}{\partial C}

and

\frac{d}{d t}\frac{\partial U}{\partial L} = \lambda \frac{\partial W}{\partial L}

with constraint

W = p C - w L = 0.

For the Lagrange multipliers we get

\lambda =-p^{-1}\alpha r^t C^{\alpha-2}F^{-\alpha}((\alpha-1)(C\dot{F}-F\dot{C})-C F \log r)

and

\lambda =w^{-1}(\alpha-1) r^t C^{\alpha-1}F^{-1-\alpha}(\alpha(C\dot{F}-F\dot{C})-C F \log r).

Equating, plugging in the constraint and dividing by C F yields

\frac{\dot{C}}{C}-\frac{\dot{F}}{F}= \frac{(\alpha w - p C)\log r}{\alpha(1-\alpha)w}

First we discuss the case r=1. Then

\frac{\dot{C}}{C}=\frac{\dot{F}}{F}

and thus (consider \frac{d}{d t}\ln C) there is a positive, constant K such that C = K F and we get because of the budget constraint

F = \frac{w}{p K + w}, C = \frac{w K }{p K + w}.

The constant K(p,w,\alpha) is unique and maximizes \int_0^T C^\alpha F^{1-\alpha} ds = \int_0^T \frac{w K^\alpha}{p K + w} ds. In equilibrium we have p = p^* and w = w^*. Maximizing  K yields \frac{d}{d K}\frac{w^* K^\alpha}{p^* K + w^*}= 0 and thus K=\frac{\alpha w^*}{(1-\alpha) p^*}. Now

F = 1-\alpha

and

C = \alpha \frac{w^*}{p^*}.

The case r<1. In equilibrium \dot{C}=\dot{F}=0 we immediately obtain C=\alpha \frac{w^*}{p^*}. Plugging this into the budget constraint yields F=1-\alpha.

Interestingly enough, we get an equilibrium equal to the solution of the time-independent model. How justified is S. Smale’s assumption C=\dot{p}? Economists often use linear demand theory and set C=T-p. Both approaches seem to be incompatible and both have a draw back. When you scale prices (e.g. by introducing a new currency) demand should stay the same. This is not the case in both settings. One needs currency dependent constants that scale accordingly to fix that. One possibility to avoid that is C=\frac{\dot{p}}{p}. As usual, more options do not improve clarity and calculating the whole model in the general case, i.e. C=C(p,\dot{p}) is not totally conclusive either. For a solution of the Euler-Lagrange equations one obtains under moderate assumptions on the partial derivatives that

\alpha (1-\alpha)w\frac{\partial C}{\partial \dot{p}}\left(\frac{\dot{C}}{C}-\frac{\dot{F}}{F}\right)  =  (\alpha w - p C)\left(\frac{\partial C}{\partial \dot{p}}\log r + \frac{d}{d t}\frac{\partial C}{\partial \dot{p}}-\frac{\partial C}{\partial p}\right).

Linear demand has \frac{\partial C}{\partial \dot{p}}=0 and thus \alpha w - p C=0. The budget constraint implies F=1-\alpha which is a constant. We thus can safely exclude linear demand from our considerations. The above equation cannot distinguish between Smale’s assumption and C=\frac{\dot{p}}{p}. However, hidden in the technical assumptions, there seems to be some advantage in Smale’s approach. It remains to clarify the price-scaling issue.


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.


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

Proposition.

\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).


I like to work

October 1, 2010

Teaching eight mathematics courses (quasi-)simultaneously is just a matter of organization. At least that is what I currently try to prove. Meanwhile I learn a lot about analytic number theory and Erdös’s discrepancy conjecture.


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)\}.