Conjecture

Bruno J. · #1 $Old$ June 28th, 2009, 01:48 PM

I posted this on another forum a while back but nobody was able to prove or disprove this conjecture of mine. I have empirical reasons to believe that it is true.

Let $A \subset \mathbb{N}$ be an infinite subset of the positive integers. Define

$f(x) = \sum_{a \in A}\frac{x^a}{a!}$ .

Prove that, as $x \rightarrow \infty$ , $f(x)^{1/x} \rightarrow e$ , or supply a counter-example.

Laurent · #2 $Old$ June 28th, 2009, 03:15 PM

Quote:

Originally Posted by Bruno J. $View Post$

Prove that, as $x \rightarrow \infty$ , $f(x)^{1/x} \rightarrow e$ , or supply a counter-example.

Neither a proof nor a counter-example, just first thoughts...

Since $f(x)\leq e^x$ , we have the right upper bound.

There is a matching lower bound: for $a\in A$ , $f(a)\geq \frac{a^a}{a!}=g(a)$ and, using $\log n!=n\log n-n+o(n)$ (consequence of Stirling formula), we obtain $g(a)^{1/a}\rightarrow e$ . Therefore, with the upper bound:

$\lim_{a\to\infty, a\in A} f(a)^{1/a}=e$ .

However, I suspect that $f(x)^{1/x}$ can fluctuate when $x$ is between two successive points of $A$ that would be "far away from each other". Allowing for arbitrary $A$ seems too weak an assumption to me: it can be an incredibly "hollow" sequence...

Can you prove the theorem for $A=\{n^2|n\in\mathbb{N}\}$ ? Or for any other sequence that grows faster than linearly? (I would be curious of what method you would use)

Laurent · #3 $Old$ June 29th, 2009, 05:50 AM

Quote:

Originally Posted by Laurent $View Post$

Neither a proof nor a counter-example, just first thoughts...

Now I have a proof that fluctuations between points of $A$ can break the conjecture. I shall provide a family of examples where $\liminf_{x\to\infty} f(x)^{1/x}\leq 1$ .

Note that $f(x)^{1/x}\to e$ is equivalent to $\frac{\log f(x)}{x}\to 1$ .

Suppose $x$ is such that $m<x<M$ where $m,M\in A$ and $A\cap(m,M)=\emptyset$ (thus $(m,M)$ is a gap in $A$ , thought of as a large gap). More precise conditions will come later.

We have the following upper bound that consists in taking all terms of the series outside the gap:

$f(x)\leq \sum_{a=0}^m \frac{x^a}{a!}+\sum_{a=M}^\infty \frac{x^a}{a!}$ .

For the first sum, note that the largest term is the last one (each term is $\frac{x}{a}(>1)$ times the previous one), so that the sum is less than $(m+1)\frac{x^m}{m!}$ .

For the second sum, I factorize by the first term and use a geometric series to bound the second factor:

$\sum_{a=M}^\infty \frac{x^a}{a!}=\frac{x^M}{M!}\left(1+\frac{x}{M+1}+\frac{x^2}{(M+1)(M+2)}+\cdots\right)$ $\leq \frac{x^M}{M!}(1+\frac{x}{M}+\frac{x^2}{M^2}+\cdots)=\frac{x^M}{M!}\frac{1}{1-\frac{x}{M}}$ .

Summarizing, we have $f(x)\leq (m+1)\frac{x^m}{m!}+\frac{x^M}{M!}\frac{1}{1-\frac{x}{M}}$ .

I shall now give conditions that ensure $\frac{log T}{x}\to 0$ or $-\infty$ where $T$ is either of the two terms of the upper bound, and the limit is taken along some sequence $x_n\to\infty$ (corresponding to some intervals $[m_n,M_n]$ ).

First one: $\frac{1}{x}\log\frac{x^m}{m!}=\frac{m\log x-\log m!}{x}=\frac{m}{x}(\log\tfrac{x}{m}+O(1))$ $=\frac{\log\frac{x}{m}}{\frac{x}{m}}+O(\frac{m}{x})$ . (Using $\log m!=m\log m+O(m)$ ), hence $\frac{1}{x}\log\frac{x^m}{m!}\to 0$ as soon as $\frac{m}{x}\to 0$ and $m\to\infty$ . (Indeed, $\frac{\log x}{x}\to_{x\to\infty} 0$ ) * I forgot $\frac{1}{x}\log(m+1)$ , which also tends to 0 (faster) under this condition.

Second one: $\frac{1}{x}\log(\frac{x^M}{M!}\frac{1}{1-\frac{x}{M}})=\frac{1}{x}(M\log x-\log M!-\log(1-\frac{x}{M}))$ $=\frac{M\log x-M\log M+M-\frac{1}{2}\log M+O(1)}{x}+\frac{1}{M}+o(\frac{1}{M})$ if $\frac{x}{M}\to 0$ and $M\to\infty$ (using Stirling estimate: $\log n!=n\log n-n+\frac{1}{2}\log n+O(1)$ and $\log(1+x)=x+o_{x\to 0}(x)$ ), hence this term equals $\frac{M}{x}(-\log\frac{M}{x}+1-\frac{1}{2}\frac{\log M}{M}x)+O(\frac{1}{x})+\frac{1}{M}+o(\frac{1}{M})$ , so that it tends to $-\infty$ as soon as $\frac{x}{M}\to 0$ and $M\to\infty$ .

Since $\log(a+b)\leq \max(\log (2a),\log (2b))=\log 2+\max(\log a,\log b)$ , we deduce that $\liminf f(x)^{1/x}\leq 1$ where the bound corresponds to a limit taken along sequences of $x$ that are in gaps $(m,M)$ of $A$ such that $m<\!\!< x<\!\!<M$ (" $<\!\!<$ " meaning "negligible compared to"). Such sequences of $x$ 's exist when $A$ grows very fast (we must have $m<\!\!<M$ where $m$ and $M$ are successive terms in the sequence): for instance, $n!<\!\!< n!\sqrt{n}<\!\!<(n+1)!$ so $A=\{n!|n\in\mathbb{N}\}$ and $x_n=n!\sqrt{n}$ is such an example.

--

However, I would still be interested in knowing how you would deal with $A=\{n^2|n\in\mathbb{N}\}$ if you know that.

Bruno J. · #4 $Old$ June 29th, 2009, 01:38 PM

Marvellous! You're a champ. I wouldn't have known how to do this myself.

I do not know how to deal with the specific case you give. I only had some empirical reasons to believe the conjecture was true - I did some tests with Mathematica and it seemed to hold with some very sparse sets...

Thanks and congrats again!

Sampras · #5 $Old$ June 29th, 2009, 01:50 PM

Quote:

Originally Posted by Bruno J. $View Post$

I posted this on another forum a while back but nobody was able to prove or disprove this conjecture of mine. I have empirical reasons to believe that it is true.

Let $A \subset \mathbb{N}$ be an infinite subset of the positive integers. Define

$f(x) = \sum_{a \in A}\frac{x^a}{a!}$ .

Prove that, as $x \rightarrow \infty$ , $f(x)^{1/x} \rightarrow e$ , or supply a counter-example.

Wouldn't $A = \mathbb{N}$ if $A$ is an infinite subset of $\mathbb{N}$ ?

Moo · #6 $Old$ June 29th, 2009, 01:58 PM

Quote:

Originally Posted by Sampras $View Post$

Wouldn't $A = \mathbb{N}$ if $A$ is an infinite subset of $\mathbb{N}$ ?

Consider the set of odd natural integers, which is an infinite subset of $\mathbb{N}$

$A$ would be isomorphic to $\mathbb{N}$ (if I'm not mistaking

)