User eric naslund - MathOverflow

Answer by Eric Naslund for Recovering $\sum_{n \leq x} a(n)$ from $\sum_{n \leq x} a(n)e^{-n/x}$

2013-03-25T16:45:57Z

A standard approach to think about is partial summation. Suppose that $A(x)=\sum_{n\leq x} a(n)$ and $S(x)=\sum_{n\leq x} a(n)e^{-n/x}$. Then we can relate these two sums in the following way:

$$\sum_{n\leq x}a(n)e^{-n/x}=\int_{1}^{x}e^{-t/x}d\left(A(t)\right)=\frac{1}{e}A(x)+\frac{1}{x}\int_{1}^{x}A(t)e^{-t/x}dx.\ \ \ \ \ \ (1) $$

$$\sum_{n\leq x}a(n)e^{-n/x}e^{n/x}=\int_{1}^{x}e^{t/x}d\left(S(x)\right)=eS(x)-\frac{1}{x}\int_{1}^{x}e^{t/x}S(t)dt.\ \ \ \ \ \ (2)$$

Equation $(1)$ shows that we can write $S(x)$ in terms of $A(x)$, and if we know an asymptotic for $A(x)$ we can recover one for $S(x)$. At first glance, $(2)$ does the same thing, but things could potentially go wrong with the negative sign, that is there could be cancellation and we would need a better expansion for $S(t)$. Since $e^{-n/x}$ is a nice factor between $1$ and $1/e$, I don't think there should be any problems with using $(2)$ for most sequences $a(n)$ that we would be interested in.

Mathematical Advice for Interested Highschool Students

2011-07-26T18:36:22Z

This may not be a research level math question, but I believe it is still relevant to Math Overflow.

What general resources exist for students in highschool who are very interested in Mathematics? What advice would you give to a young student to encourage them, and nurture their interest in mathematics? If a young high school student came to you and said they were very interested in math, and wanted to know what to do to keep learning, what would you tell them?

Thank you for your help,

Integer Points on the Elliptic Curve $y^2=x^3+17$.

2011-01-23T18:07:45Z

I came across the problem "find all integer solutions to $y^2=x^3+17$."

I've tried several things, without any success, and I was hoping that someone could help out. (Some ideas or a reference for where to find it are both appreciated)

By numerical calculation I have found that the following integer points $(x,y)$ lie on the curve

$(-1,4)$, $(-2,3)$, $(2,5)$, $(4,9)$, $(8,23)$, $(43,282)$, $(52,375)$, $(5234,378661)$ and this is probably all of them.

Thanks

Answer by Eric Naslund for How to rewrite this totient summation in terms of Mertens?

2013-03-01T04:42:55Z

Since $\varphi(n)=n\sum_{d|n}\frac{\mu(d)}{d},$ by switching the order of summation we have that for fixed $l$ $$\sum_{n\leq x}\varphi(n)n^{l}=\sum_{kd\leq x}\mu(d)k^{l}d^{l}k$$

$$=\sum_{k\leq x}k^{l+1}\sum_{d\leq\frac{x}{d}}\mu(d)d^{l}.$$ Now, $$\sum_{d\leq y}\mu(d)d^{l}=\int_{0}^{y}t^{l}d\left(M(t)\right)=M(y)y^{l}-l\int_{0}^{y}M(t)t^{l-1}dt,$$ so you can write $$\sum_{n\leq x}\varphi(n)n^{l}=\sum_{k\leq x}k^{l+1}\left(\frac{x}{k}\right)^{l}M\left(\frac{x}{k}\right)-l\int_{0}^{\frac{x}{k}}t^{l-1}M(t)dt.$$ This may be rearranged as

$$x^{l}\sum_{k\leq x}kM\left(\frac{x}{k}\right)-l\sum_{k\leq x}k^{l+1}\int_{0}^{\frac{x}{k}}t^{l-1}M(t)dt,$$ which is equal to

$$x^{l}\sum_{k\leq x}kM\left(\frac{x}{k}\right)-l\int_{0}^{x}t^{l-1}\sum_{k\leq x}k^{2}M\left(\frac{t}{k}\right)dt.$$

Riemann Zeta Function connection to Quantum Mechanics.

2011-02-06T06:36:36Z

I feel like this question is probably wrong for MO, (too low level, perhaps unclear) but my curiosity has got the better of me:

I hear that the Riemann Zeta Function and its zeros have applications to quantum mechanics, as well as other fields. I do not understand these connections, and because of this the following question came up:

In theory, is it possible through physical experiments (particle experiments) to approximately calculate the first few zeros of the Riemann zeta function?

In other words, (using the explicit formula) could we write down the $n^{th}$ prime number (up to a given margin of error/probability of correctness) only from doing quantum mechanical experiments?

(If there are conjectures/facts that we cannot prove, but would answer the question, I would be happy to hear those too)

Thanks!

Answer by Eric Naslund for Using Quotient of Prime Numbers to Approximation Reals

2012-12-25T09:02:17Z

Question 1: The set is dense.

Suppose that we are given a fixed $x\in\mathbb{R}$. Then let $p$ be a large prime. If $p$ is sufficiently large, then there will be a prime $$q\in\left[px,\ px+\left(px\right)^{0.525}\right]$$ by the work of Baker, Harman and Pintz on prime gaps. This implies that $$\left|x-\frac{q}{p}\right|\ll_x p^{-0.475},$$ which becomes arbitrarily small as we take $p\rightarrow\infty $. This proves that for any $\epsilon>0$, there exists $p,q$ such that $\left|x-\frac{q}{p}\right|\leq \epsilon.$

Question 2: We can find infinitely many solutions to $$1\leq qp-rs\leq a$$ for primes $p,q,r,s$ and all $a\geq 26$. Under the Elliott-Halberstam Conjecture, we can take $a\geq 6$.

This is a corollary of the work of Goldston, Graham, Pintz and Yıldırım on the gaps between almost primes. They prove that if $q_n$ is the $n^{th}$ almost prime, then $$\liminf_{n\rightarrow \infty} q_{n+1}-q_n \leq 26,$$ and that the upper bound may be reduced to $6$ under the Elliott-Halberstam Conjecture. Since $q_n=pq$ and $q_{n+1}=rs$ where $p,q,r,s$ are primes, this yields the above claim.

Edit: The more recent work of Goldston, Graham, Pintz and Yıldırım show that we can take $a=6$ unconditionally. (Thank you to quid for mentioning this in the comments)

Answer by Eric Naslund for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

2012-12-14T04:14:07Z

Asymptotics: Lets look at the quantity

$$S(n)=(-1)^{n}(n+1)\binom{i}{n+1}=i\prod_{k=1}^{n+1}\left(1-\frac{i}{k}\right).$$ It's just your binomial coefficient above with the $(-1)^{n+1}$ factored in, and an extra $n+1$ so it factors nicely as a product.

Claim: We have that

$$S(n)=\sqrt{\frac{\sinh{\pi}}{\pi}}e^{iC_{0}}e^{-i\log n}\left(1+O\left(\frac{1}{n}\right)\right),$$ where

$$C_{0}=\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx =\arg(\Gamma(i))\approx -1.872.$$

In particular, the angle moves around the circle like $\log n$.

Application to your question: The above claim shows that $$f_{n+1} = (-1)^{n+1} n! \sqrt{\frac{\sinh{\pi}}{\pi}}\cos(-\log n+C_0)\left(1+O\left(\frac{1}{n}\right)\right)$$ and $$g_{n+1} \sim (-1)^{n+1} n! \sqrt{\frac{\sinh{\pi}}{\pi}} \sin(-\log n+C_0)\left(1+O\left(\frac{1}{n}\right)\right).$$

In particular, the ratio $g_n/f_n$ can be made arbitrarily large or small.

Proof of the claim: We first note that the size is

$$\sqrt{\prod_{k=1}^{n}\left(1+\frac{1}{k^{2}}\right)}=\sqrt{\prod_{k=1}^{\infty}\left(1+\frac{1}{k^{2}}\right)}+O\left(\frac{1}{n}\right).$$ To evaluate this product, recall the Weierstrass product for the Gamma function $$\left(\Gamma(z)\right)^{-1}=ze^{\gamma z}\prod_{k=1}^{\infty}\left(1+\frac{z}{k^{2}}\right)e^{-\frac{z}{r}}.$$ From this it follows that $$\frac{1}{|\Gamma(i)|^{2}}=\frac{1}{\Gamma(i)\Gamma(-i)}=\prod_{k=1}^{\infty}\left(1+\frac{1}{k^{2}}\right).$$ Using the identity $$\Gamma(x)\Gamma(-x)=-\frac{\pi}{x\sin\left(\pi x\right)},$$ we now have that $$\frac{1}{\Gamma(i)\Gamma(-i)}=\frac{-i\sin(i\pi)}{\pi}=\frac{\sinh(\pi)}{\pi},$$ which gives rise to the $\sqrt{\frac{\sinh(\pi)}{\pi}}$ term. Moving on to the evaluation of the angle, by looking at each triangle, and noting that the argument is additive when multiplied, we get that the argument equals

$$-\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right).$$

The negative sign arises since we are working in the fourth quadrant. By looking at the Taylor series for $\tan^{-1}$ we see that the above is $\log n+O(1)$, however, I would like to compute this argument more precisely, and obtain the constant. Lets compare our $\tan^{-1}$ series to the harmonic series. Rewriting things in terms of a Riemann Stieltjes integral, and using summation by parts, we have that

$$\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right)=\int_{0}^{n}\tan^{-1}\left(\frac{1}{x}\right)d\left[x\right]=[n]\tan^{-1}(1/n)\int_{0}^{n}\frac{\left[x\right]}{1+x^{2}}dx. $$

Pulling out the main term with the identity $[x]=x-\{x\}$, the above equals

$$\int_{0}^{n}\frac{x}{1+x^{2}}dx-\int_{0}^{n}\frac{\{x\}}{1+x^{2}}dx.$$

Since the first integral evaluates to $\frac{1}{2}\log(1+x^2)$, we have that $$\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right)=\log n +1-\int_0^\infty \frac{\{x\}}{1+x^2}dx +O\left(\frac{1}{n}\right).$$

Acknowledgements: I would like to thank Noam Elkies for pointing out that $$\prod_{k=1}^\infty \sqrt{1+\frac{1}{k^2}}=\frac{1}{|\Gamma(i)|}=\sqrt{\frac{\sinh(\pi)}{\pi}}$$ in the comments.

Edit: Fixed the constants appearing. Interestingly $$\Gamma(i)=\sqrt{\frac{\pi}{\sinh{\pi}}}\exp\left(i\left(\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx \right)\right).$$

Answer by Eric Naslund for A curious limit involving prime numbers and composite numbers

2012-01-09T05:44:34Z

The sums above are Riemann sums over different partitions for the function $\arctan(x)$ between $x=0$ and $x=1$, so the limit will equal the integral which is $\frac{\pi}{4}$. Both of these converge to the same value because they are not too weirdly distributed among $[0,1]$.

Remark: We need to use the fact that there exists $\theta<1$ with $p_n-p_{n-1}\ll p_n^\theta$. (we can take $\theta=7/12$) For the primes, we know that this tells us that if $j\geq n^{7/12+\epsilon}$, then $$p_{n+j}-p_{n}\sim j\log n. $$

Edit: I added why $p_{n+j}-p_{n}\sim j n^{7/12}$ for $j\geq n^{7/12+\epsilon}$ is important after reading some of the comments. It tells us/(or actually comes from) how things will look in short intervals for primes. It is not true that for general sequences with $\alpha_{i}-\alpha_{i-1}\ll n^{-\delta}$ the Riemann sum works out, rather for sequences where sums over short intervals is very close to the identity function.

Edit 2: This is more of a remark because I have a feeling someone will wonder about this. The reason why we need it to be close to the identity on short intervals is because we are weighting with the identity, $\frac{1}{n}$, rather then $x_i-x_{i-1}$ which is what is used in the definition of the Riemann integral. Summation tricks to move to these short intervals allows us to make the desired conclusion. Note that the limit will hold for any bounded monotonic integrable $f$, and any sequence satisfying the condition.

Answer by Eric Naslund for There are two points on the Earth's surface that ... ?

2012-11-18T01:49:10Z

We can say the following:

"At any given time, there are two points on the earth exactly 20 000 km apart with the same exact same temperature and barometric pressure."

I am making a few assumptions, but do note that the distance from the north pole to the south pole is 20 000 km. Indeed, in the Wikipedia article which you linked to in your question, we find the quote:

"The case n = 2 is often illustrated by saying that at any moment there is always a pair of antipodal points on the Earth's surface with equal temperatures and equal barometric pressures. This assumes that temperature and barometric pressure vary continuously."

Answer by Eric Naslund for Primes with more ones than zeroes in their Binary expansion

2012-05-18T19:20:41Z

We can take $f(n)=\alpha n$ for any $\alpha<0.7375$. In particular, the set of primes with more than twice as many ones that zeros in their binary expansion is infinite.

I posted a short article on the arXiv which deals with exactly this kind of problem. Let $s_2(n)$ denote the sum of digits base $2$. Since $x$ has approximately $\log_2(x)$ binary digits, we are looking at when $s_2(n)\geq \alpha \log_2 (n)$. In that 4 page note we prove that

$$\left|\left\{ p\leq x,\ p\ \text{prime}\ : s_2(n)\geq \alpha\log_2(x) \right\} \right|\gg_{\epsilon}\ x^{2\left(1-\alpha\right)}e^{-c\left(\log x\right)^{1/2+\epsilon}}.$$

Moreover, such a result extends naturally to base $q$, yielding the bound

$$\left|\left\{ p\leq x,\ p\ \text{prime}\ :\ s_{q}(p)\geq\alpha(q-1)\log_{q}(x)\right\} \right|\gg_{\epsilon}\ x^{2\left(1-\alpha\right)}e^{-c\left(\log x\right)^{1/2+\epsilon}}$$ where $s_q(n)$ is the sum of digits of $n$ in base $q$.

The proof takes advantage of the fact that the multinomial distribution is sharply peaked. The number $0.7375$ appears because $1-0.525/2=0.7375$, and $0.525$ is the exponent appearing in Baker Harman and Pintz's work on prime gaps.

Edit: At some point, I deleted my answer because I was unsatisfied with it. It has now been improved significantly.

Answer by Eric Naslund for Knight tour prime (conjecture)

2012-05-08T19:41:03Z

We can prove something stronger, that there is no path at all. (That is removing the Hamiltonian condition) What follows is a proof for sufficiently large $n$. The proof makes use of the prime number theorem, a corollary of the Selberg sieve, and a result concerning prime gaps.

Proof: We proceed by contradiction.

$n$ odd: If $n=2k+1$, then we may color the board as a checkerboard. Note that odd squares will always be the same color, and even squares will always be the same color. Since the knight alternates colors on each jump, and there is only one even prime, the result follows.

$n$ even: If $n=2k$, we similarly color the odd squares white, and the even squares black. Ignore the prime 2, so that all primes we are dealing with are odd. This means that if we are on a white square, we must jump to a white square. If we are on the first row, this tells us that the knights next move must be a jump to the second row, either two to the left, or two to the right.

Key Idea: Since we must jump from the first row to the second, this means if we can avoid double counting, there are at least the same number of primes in the second row as in the first. However, the second row contains larger numbers, and the density of the primes decreases as we go to infinity. In particular, if $x<n$ , the density of the primes in the interval $[n+1,n+x]$ will be smaller then the density of the primes in $[1,x]$ . Since $[n+1,n+x]$ is in the second row, and $[1,x]$ is in the first row, this contradicts the fact that the second row should have more primes.

Consider the set $\mathcal{P}_x$ to be the set primes less then $x$ where we have thrown out all pairs of primes $p,p+2\in \mathcal{P}$ and $p,p+4\in \mathcal{P}$. We throw out these pairs to avoid double counting. By using the Selberg sieve results, we know that are $\ll \frac{x}{\log^2 x}$ such pairs, and so it follows that $$|\mathcal{P}_x| \sim \frac{x}{\log x}$$ as $x\rightarrow \infty$. Now, choose $x\leq n$ so that all the elements of $\mathcal{P}_x$ lie in the first row. Assuming the path exists, we must have a prime in the second row within jumping distance for each prime in the first row. By the condition that we have no pairs of the form $p,p+2$, or $p,p+4$ in our set, we see that among the integers $[n,n+x]$ we must have at least $|\mathcal{P}_x|$ primes. (The condition regarding prime pairs makes sure that no prime in the second row is used as the jumping point for two distinct primes in the first row.) Heath-Brown showed that $$\pi(n+n^{7/12})-\pi(n)\sim \frac{n^{7/12}}{\log n},$$ (we can use a weaker result then this) so taking $x=n^{7/12}$ we see there are $\frac{n^{7/12}}{\log n}$ primes in the interval $[n,n+x]$. However, we had bounded this quantity below by $|\mathcal{P}_x|\sim \frac{n^{7/12}}{\log n^{7/12}}$, and this gives the asymptotic inequality $$\frac{n^{7/12}}{\log n} \gtrsim \frac{12}{7} \frac{n^{7/12}}{\log n},$$ which is evidently false.

Remark: We need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta<1$, $\theta=\frac{7}{12}$ is much stronger than what is required.

Remark 2: If we wanted only to prove the conjecture for Hamiltonian paths, we did not need to spend time removing the twin primes pairs for fear of double counting, since a Hamiltonian path by definition implies we cannot double count.

Remark 3: It is quite likely that there is a clever elementary approach to solving the problem when $n$ is even.

Answer by Eric Naslund for The tightest prime zipper

2012-11-10T01:14:03Z

The slowest growing zipper will depend on the size of $p_{n+1}-p_n$ where $p_n$ is the $n^{th}$ prime number. There are many results regarding the size of the largest prime gap.

Unconditional: The work of Baker, Harman and Pintz shows that $$p_{n+1}-p_n \ll p_n^{0.525}$$ for some computable constant. This means that your zipper function may be taken to be $f(n)=Cn^{40/19}$ for some constant $C$. The $\frac{40}{19}$ appears in the exponent because $\frac{40}{19}=\frac{1}{1-0.525}$.

Conditional: If we assume the Riemann Hypothesis, then we have $$ p_{n+1}-p_n \ll \sqrt {p_n}\log p_n,$$ and we may take $f(n)=n^2 \log n$. Assuming Cramer's conjecture, which says that $$p_{n+1}-p_n =O\left((\log p_n)^2\right),$$ would allows us to take $f(n)=Cn(\log n)^2$ for some constant $C$.

Also see this Wikipedia article on prime gaps.

Remark: Note that finding a prime zipper which grows slower than $f(n)=Cn^{40/19}$ would imply better bounds on the largest prime gap, so your question is equivalent to asking what is the largest prime gap.

** Avoid pointless functions such as $f(n)=p_n+1$.

Answer by Eric Naslund for Question on consecutive integers with similar prime factorizations

2012-11-09T18:06:28Z

This question is directly related to when $d(n)=d(n+1)$ where $d(n)$ denotes the divisor function.

Solutions to $d(n)=d(n+1)$:

In 1952, Erdos and Mirsky conjectured that $d(n)=d(n+1)$ has infinitely many solutions. In 1984, Heath Brown proved this result, and gave a lower bound on the counting function. Let $\widetilde{D}(x)$ denote the number of $n\leq x$ satisfying $d(n)=d(n+1)$. Heath Brown showed that $$\widetilde{D}(x)\gg \frac{x}{(\log x)^7}.$$

In 1987 Erdős, Pomerance and Sárközy gave the upper bound $$\widetilde{D}(x)\ll \frac{x}{(\log \log x)^\frac{1}{2}}.$$

Later that year, Hildebrand improved Heath Browns Result that $$\widetilde{D}(x)\gg \frac{x}{(\log \log x)^3},$$ showing that the correct magnitude involves a doubly logarithmic factor.

Consecutive integers with identical prime signature:

Let $\widetilde{\mathcal{P}}(x)$ denote the number of integers $n\leq x$ such that $n$ and $n+1$ have the same prime signature. Then $\widetilde{\mathcal{P}}(x)\leq \widetilde{D}(x)$, and so Erdős, Pomerance and Sárközy result immediately implies that $$\widetilde{\mathcal{P}}(x)\ll \frac{x}{(\log \log x)^\frac{1}{2}}.$$ This means that the counting function is not linear even though the graph resembles a straight line. ($\log \log x$ grows extremely slowly, and is nearly unnoticeable)

Since $d(n)=d(n+1)$ "often" implies that $n$ and $n+1$ have the same signature, it seems likely that one could use Hildebrands lower bound to prove that the set of consecutive integers with identical prime signature is infinite. Bounding the number of times we have $d(n)= d(n+1)$, yet difference signatures, seems like a fruitful approach.

Some References: (Chronological Ordering)

Erdös, Mirsky 1952: The distribution of the values of $d(n)$.
Heath-Brown 1984: The divisor function at consecutive integers.
Erdős, Pomerance and Sárközy 1987: On locally repeated values of certain arithmetic functions. III.
Hildebrand 1987: The divisor function at consecutive integers.

Answer by Eric Naslund for An application of Mobius Inversion in a paper of Shintani

2012-10-13T23:37:06Z

Let $g(n)$ denote the indicator function for the fourth powers. Then your sum equals

$$\sum_{n\leq x}\left(h_{r}*g\right)(n),$$

where $*$ denotes Dirichlet convolution. We may rewrite the given asymptotic as

$$\sum_{k\leq x}g(k)\sum_{n\leq\frac{x}{k}}h_{r}(n)=2^{-1}\zeta(2)\zeta(4)x+O\left(x^{2/3+\epsilon}\right),$$

noticing that this is of the form

$$G(x)=\sum_{n\leq x}\alpha(n)F\left(\frac{x}{n}\right).$$

Mobius inversion tells us that

$$F(x)=\sum_{n\leq x}\alpha^{-1}(n)G\left(\frac{x}{n}\right),$$

where $\alpha^{-1}$ is the multiplicative inverse of $\alpha$ with respect to Dirichlet convolution. Applying Mobius inversion to our sum, we have that

$$\sum_{n\leq x}h_{r}(n)=\sum_{j^{4}\leq x}\mu(j)\sum_{n\leq\frac{x}{j^{4}}}\left(h_{r}*g\right)(n)$$

which equals

$$2^{-1}\zeta(2)\zeta(4)x\sum_{j^{4}\leq x}\frac{\mu(j)}{j^{4}}+O\left(x^{2/3+\epsilon}\left(\sum_{j^{4}\leq x}\frac{1}{j^{4}}\right)\right)$$

$$=2^{-1}\zeta(2)x+O\left(x^{2/3+\epsilon}\right).$$

Notice that the Dirichlet inverse to the function $g(n)$, the indicator function for the fourth powers, is in some sense the mobius function on fourth powers.

Answer by Eric Naslund for The Inverse of the Euler Totient Function

2012-10-13T03:53:35Z

I assume you are asking about $N(m)$, the number of distinct integers $n$ which satisfy $\phi(n)=m$ where $\phi$ is the Euler Totient function.

There are many results regarding upper and lower bounds for the size of $N(m)$, as well as the mean and variance. In particular, Carmichael conjectured that $N(m)$ is never equal to $1$.

Pomerance gave the upper bound $$N(m)\leq m\exp{-(1+o(1))\log m \frac{\log \log \log m}{\log \log m}}$$ and also showed that there are infinitely many $m$ for which $$N(m)\geq m^{\frac{5}{9}}.$$

Bateman showed that $$\sum_{m\leq x} N(m)=\frac{\zeta(2)\zeta(3)}{\zeta(6)}x+O\left(xe^{-c\sqrt{\log x\log \log x}}\right),$$ and we also have that $$\sum_{m\leq x} N(m)-\frac{\zeta(2)\zeta(3)}{\zeta(6)}x=\Omega\left(x^\frac{5}{9}\right)$$

For more details, see the following paper of Pomerance: Popular Values of Euler's Function.

Answer by Eric Naslund for Number of elements in the set {1,...,n}*{1,..,n}

2012-10-05T17:29:28Z

This question is known as the multiplication table problem, and was originally posed by Erdos in 1955. Erdos proved that $|A_n|=o(n^2)$, and this was sharpened by Tenenbaum in 1984. In 2008, Ford gave the exact magnitude and proved that $$\left|\{a\cdot b:\ a,b\leq N\}\right|\asymp \frac{N^2}{(\log N)^c(\log\log N)^{3/2}}$$ where $$c=1-\frac{(1+\log \log 2)}{\log 2}.$$

In 2010 Koukoulopoulos gave multidimensional generalizations of Ford's result, proving that $$\left|\{a_1\cdots a_k\ :\ a_i\leq N \text{ for all } \ i\}\right|\asymp \frac{N^{k+1}}{(\log N)^{c_k}(\log\log N)^{3/2}}$$ where $$c_{k}=\int_{1}^{\frac{k}{\log(k+1)}}\log x\text{d}x=\frac{\log(k+1)+k\log\left(k\right)-k\log\log(k+1)-k}{\log(k+1)}.$$

Some references:

Ford 2008: The distribution of integers with a divisor in a given interval. arXiv link
Koukoulopoulos 2010: Localized Factorization of Integers. arXiv link
Koukoulopoulos 2012: On the number of integers in a generalized multiplication table. arXiv link

Remark: The dates used above refer to the publication dates. (Not necessarily the date posted to the arXiv)

Answer by Eric Naslund for Problems with the divisor function in a summation

2012-09-04T00:21:40Z

First, unraveling the floor function your sum is the same as $$\sum_{d\leq x}\left(1*\mu\tau\right)(d)$$ where $*$ represents mobius convolution. Let $f(n)$ denote the above multiplicative function. Then $f(1)=1$, and $f(p^k)=-1$ for $k\geq 2$.

This means that $f=\mu$, Mobius function, on all but the prime powers, and you can deduce that $$\sum_{d\leq x}\mu(d)\tau(d)\left[\frac{x}{d}\right]\ll \frac{x}{\log x}.$$

Added: There are many ways to prove this last statement, but allow me to outline one you may not have seen. I won't make things too precise, I encourage you to look up the papers of the authors mentioned below.

Granville and Soundararajan define the distance up to $x$ between two bounded multiplicative functions $f,g:\mathbb{N}\rightarrow \mathbb{U}$ to be $$\mathbb{D}(f,g,x)=\sum_{p\leq x} \frac{1-\text{Re}f(p)\bar{g}(p)}{p}.$$ This distance tells us an enormous amount about what the mean of a multiplicative function will look like. If two functions are close together, then their means will be close as well. More remarkably, a Theorem of Halasz tells us that unless the distance between $f$ and $n^{it}$ is close for some $|t|\ll \log x$, the mean of $f$ will go to $0$, that is $\sum_{n\leq x}f(n)=o(x)$. In other words, the only bounded multiplicative functions with a nonzero mean are really close to $n^{it}$ for some $t$.

Answer by Eric Naslund for Better error bounds for partial sums of reciprocals of primes?

2012-07-20T07:31:08Z

Up to a factor of logarithm, $E(x)$'s oscillation has an amplitude which is of the same magnitude as that of $\frac{1}{x}\left(\psi(x)-x\right)$, that is the error in the prime number theorem. Specifically $$E(x)=O\left( e^{-c(\log x)^{3/5-\epsilon}}\right)$$ unconditionally, and $$E(x)=O\left( x^{-\frac{1}{2}+\epsilon}\right).$$ under RH.

Proof: Let $W(x)=\pi(x)-\text{li}(x)$ be the error term in the prime number theorem. Then

$$\sum_{p\leq x}\frac{1}{p}=\int_{2}^{x}\frac{1}{t}d\left(\pi\left(t\right)\right)=\int_{2}^{x}\frac{1}{t\log t}dt+\int_{2}^{x}\frac{1}{t}dW(t).$$

Integration by parts yields

$$\int_{2}^{x}\frac{1}{t}dW(t)=\frac{W(t)}{t}\biggr|_{2}^{x}+\int_{2}^{x}\frac{W(t)}{t^{2}}dt.$$

Since

$$\int_{2}^{x}\frac{W(t)}{t^{2}}dt=\int_{2}^{\infty}\frac{\pi(t)-\text{li}(t)}{t^{2}}dt+O_{\epsilon}\left(e^{-c\left(\log x\right)^{\frac{3}{5}-\epsilon}}\right),$$

it then follows that $$\sum_{p\leq x}\frac{1}{p}=\log\log x+b+O_{\epsilon}\left(e^{-c\left(\log x\right)^{\frac{3}{5}-\epsilon}}\right),$$

where $b=\int_{2}^{\infty}\frac{\pi(t)-\text{li}(t)}{t^{2}}dt+\frac{W(2)}{2}-\log\log2.$

Repeated Second Eigenvalue of the Adjacency Matrix of a Graph

2012-07-04T17:35:21Z

This question is motivated by a talk I went to earlier today.

Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$.

Let $$\lambda_1\geq \lambda_2 \geq\dots \geq \lambda_n$$ be the eigenvalues of $A$, so in particular $\lambda_1=d$. If the first two eigenvalues are the same, that is $\lambda_2=\lambda_1$, then it tells us a lot about the structure of the graph. In particular, the graph must be disconnected. (This is an if and only if condition)

What if the second and third eigenvalues are equal? That is, suppose that $\lambda_1>\lambda_2=\lambda_3$. What does that tell us (if anything) about the structure of the graph?

Additional questions: If $\lambda_1=\lambda_2=\cdots=\lambda_k<\lambda_{k+1}$, then the graph will have exactly $k$ connected components. What can we say about $G$ if $\lambda_1<\lambda_2=\cdots=\lambda_{k+1}<\lambda_{k+2}$? That is, the second eigenvalue has multiplicity $k$.

What if the $n^{th}$ eigenvalue has multiplicity $k$?

Answer by Eric Naslund for Median largest-prime-factor

2012-07-03T08:41:47Z

I posted a paper to the arXiv which deals with this question along with some other things.

Using some results regarding either the mean of $\omega(n)$, or integers without large prime factors, we can prove that $$M(x)=e^{(\gamma-1)/\sqrt{e}}x^{1/\sqrt{e}}\left(1+O\left(\frac{1}{\log x}\right)\right),$$ where $\gamma$ is the Euler Mascheroni constant.

More specifically, if we let $\text{li}_f(x)=\int_2^x \frac{\{x/t\}}{\log t} dt$, then $$M(x)=x^{\frac{1}{\sqrt{e}}\exp\left(-\frac{\text{li}_f(x)}{x}\right)}\left(1+O\left(e^{-c\sqrt{\log x}}\right)\right).$$ (In case the TeX is not readable, the exponent of $x$ in the above equation is $\frac{1}{\sqrt{e}}\exp\left(-\frac{\text{li}_f(x)}{x}\right)$.)

This function $\text{li}_f(x)$ has the asymptotic expansion $$\text{li}_f(x)=c_0 \frac{x}{\log x}+c_1 \frac{x}{\log^2 x}+\cdots+c_{k-1} \frac{(k-1)!x}{\log^k x}+O\left(\frac{x}{\log^{k+1}(x)}\right),$$

where $$c_k=1-\sum_{j=0}^k\frac{\gamma_k}{k!},$$ and $\gamma_k$ denotes the $k^{th}$ Stieltjes constant.

Answer by Eric Naslund for Logarithmic Integral of n^Zeta Zeroes and certain nested sums of the fractional part function

2012-06-05T21:21:06Z

Your above identity stems from $$\text{li(x)}-\Pi(x)+\text{small}=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \log \left((s-1)\zeta(s)\right)\frac{x^s}{s}ds,$$ and a Taylor expansion of the logarithm. What follows is not an exact answer to your question, it is not clear what can or cannot be done with a particular identity. Instead, we give an alternate derivation which lives more in the realm of Dirichlet series and contour integrals, but I think it will shed some light upon the problem. The identity you gave above is essentially an expansion of the logarithm in the classical identity above.

Notation: Let $\Pi(x)=\sum_{n\leq x}\frac{\Lambda(n)}{\log n}$ denote Riemann's Pi function, that is $$\Pi(x)=\pi(n)+\frac{1}{2}\pi\left(n^{\frac{1}{2}}\right)+\frac{1}{3}\pi\left(n^{\frac{1}{3}}\right)+\cdots,$$ and define $$H_{k}(x):=\sum_{j_{1}=2}^{x}\sum_{j_{2}=2}^{\lfloor\frac{x}{j_{1}}\rfloor}\cdots\sum_{j_{k}=2}^{\lfloor\frac{x}{j_{1}\cdots j_{k-1}}\rfloor}1$$ to be the number of integer points under hyperbola with entries greater than $2$, and let $$I_{k}(x)=\int_{1}^{x}\int_{1}^{\frac{x}{y_{1}}}\cdots\int_{1}^{\frac{x}{y_{1}\cdots y_{k-1}}}1\text{d}y_{1}\cdots\text{d}y_{k}$$ be the same area when integrated.

Lets begin by looking at the generalized divisor problem. Using Perrons formula, for any $a>1$ we have that $$D_{k}(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\zeta(s)^{k}\frac{x^{s}}{s}ds,\ \ \ \ \ \ \ \ \ \ (1)$$ where $D_{k}(x)$ is the sum of the generalized divisor function. $D_{k}(n)$ is exactly the number of integer points under the $k$-dimensional hyperbola $x_{1}\cdots x_{k}=n,$ but our sums start at $2$ instead of $1$ so we need to modify things slightly. To get the sum of the integer points whose smallest entry is larger than $2,$ we have to subtract away the $k$ different $(k-1)$-dimensional hyperbolas, and look at $D_{k}(n)-kD_{k-1}(n).$ However this overcompensates, and we have to add back in the $\binom{k}{2}$ different $(k-2)$-dimensional hyperbolas. Continuing in this way, we see that

$$\sum_{j=0}^{k}\binom{k}{j}(-1)^{j}D_{k-j}(n)=H_{k}(n) \ \ \ \ \ \ \ \ \ \ (2)$$

and hence equation (1) and (2) together imply that $$H_{k}(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\left(\zeta(s)-1\right)^{k}\frac{x^{s}}{s}ds. \ \ \ \ \ \ \ \ \ \ (3)$$

Similarly, in your note you proved that $$I_k(x)=x\sum_{j=1}^{k}\frac{\left(\log x\right)^{k-j}}{(k-j)!}(-1)^{j},$$ and noticing the similarities in expansions, we may rewrite this as $$I_k(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \frac{x^s}{s} \frac{1}{(s-1)^k}ds.\ \ \ \ \ \ \ \ \ (4)$$

Using (3) and (4), it follows the individual terms are $$\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \frac{x^s}{s} \left((\zeta(s)-1)^k-\frac{1}{(s-1)^k}\right)ds.$$ Summing over $k$, and using absolute convergence to switch orders, we have that $$\sum_{k=1}^\infty \frac{(-1)^k}{k}\left(H_k(x)-I_k(x)\right)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\sum_{k=1}^\infty \frac{(-1)^k}{k}(\zeta(s)-1)^k \frac{x^s}{s}ds+$$ $$\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\sum_{k=1}^\infty \frac{(-1)^k}{k}(s-1)^{-k} \frac{x^s}{s}ds.$$

Removing the series expansion for the logarithm, this is

$$=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\left(-\log\zeta(s)\right)\frac{x^{s}}{s}ds+\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}-\log\left(\frac{s-1}{s}\right)\frac{x^{s}}{s}ds.$$ And using Perrons formula once again, since $$-\log\zeta(s)=\sum_{k}\frac{\Lambda(n)}{\log n}n^{-s},$$ we have shown that $$\sum_{k=1}^\infty \frac{(-1)^k}{k}H_k(x)=\Pi(x),$$ and on the other hand the integral $$\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty} \log(s-1)\frac{x^s}{s} ds$$ gives rise to the $\text{li}(x)$ term.

Answer by Eric Naslund for an equation in fractions

2012-06-05T12:37:57Z

Solving this equation is equivalent to finding the zeros of the derivative of a rational function, based only on knowing only the rational function's factorization.

Let $$Q(x)=\prod_{i=1}^{n}\left(x-\alpha_{i}\right)\prod_{i=1}^{m}\left(x-\beta_{i}\right)^{-1}.$$ Then taking the logarithmic derivative we find that $$\frac{Q^{'}(x)}{Q(x)}=\sum_{i=1}^{n}\frac{1}{x-\alpha_{i}}-\sum_{i=1}^{m}\frac{1}{x-\beta_{i}},$$ and so the equation $$\sum_{i=1}^{n}\frac{1}{x-\alpha_{i}}=\sum_{i=1}^{m}\frac{1}{x-\beta_{i}}$$ is solved if and only if $\frac{Q^'(x)}{Q(x)}=0$. At any point where the denominator has a pole of degree $k$, the numerator will have a pole of degree $k+1$, and so the numerator has no contribution to the number of zeros of $\frac{Q^'(x)}{Q(x)}$.

Thus, we find that $\sum_{i=1}^{n}\frac{1}{x-\alpha_{i}}=\sum_{i=1}^{m}\frac{1}{x-\beta_{i}}$ if and only if $Q^'(x)=0$, and there are many existing resources for this kind of problem. (For example to do this numerically one can use Newtons method.)

Answer by Eric Naslund for q-Pochhammer Symbol Identity

2012-05-07T18:44:28Z

The equality is indeed correct. It follows from identities in Ramanujan's notebook.

First notice that $\left(-1;e^{-4\pi}\right)_{\infty}^{2}=2\left(-e^{-4\pi};e^{-4\pi}\right)_{\infty}^{2},$ so we are trying to prove the identity

$$\frac{\left(-e^{-4\pi};e^{-4\pi}\right)_{\infty}^{2}}{\left(e^{-2\pi};e^{-2\pi}\right)_{\infty}^{4}}=\frac{16\pi^{3}\left(\sqrt{2}-1\right)\sqrt{2^{\frac{1}{4}}+2^{\frac{3}{4}}}}{\Gamma^{4}\left(\frac{1}{4}\right)}.$$

The right hand side many be cleaned up further, and written as

$$\frac{32\pi^{3}2^{\frac{1}{8}}\sqrt{\sqrt{2}-1}}{\Gamma^{4}\left(\frac{1}{4}\right)}.$$

Now, since $1+q^{4}=\frac{1-q^{8}}{1-q^{4}},$ the left hand side is

$$\frac{\left(e^{-8\pi};e^{-8\pi}\right)_{\infty}^{2}}{\left(e^{-4\pi};e^{-4\pi}\right)_{\infty}^{2}\left(e^{-2\pi};e^{-2\pi}\right)_{\infty}^{4}}=\frac{\left(e^{-8\pi}\right)_{\infty}^{2}}{\left(e^{-4\pi}\right)_{\infty}^{2}\left(e^{-2\pi}\right)_{\infty}^{4}}.\ \ \ \ \ \ \ \ \ \ (1)$$

On page 326 of Bruce C Brendts “Ramanujan's Notebook Part V” he shows that

$$\left(e^{-2\pi}\right)_{\infty}=\frac{\Gamma\left(\frac{1}{4}\right)}{2\pi^{\frac{3}{4}}}e^{\frac{\pi}{12}}$$

$$\left(e^{-4\pi}\right)_{\infty}=\frac{2^{-\frac{3}{8}}\Gamma\left(\frac{1}{4}\right)}{2\pi^{\frac{3}{4}}}e^{\frac{\pi}{6}}$$ and

$$\left(e^{-8\pi}\right)_{\infty}=\frac{2^{-\frac{13}{16}}\Gamma\left(\frac{1}{4}\right)}{2\pi^{\frac{3}{4}}}\left(\sqrt{2}-1\right)^{\frac{1}{4}}e^{\frac{\pi}{3}}.$$

Combining these three together in equation (1) yields the desired result.

Remark: You could have proceeded in a different manner by noticing that the denominator is (almost) the Dedkind eta function. The product can be written as

$$\frac{\left(-e^{-4\pi};e^{-4\pi}\right)_{\infty}^{2}}{\left(e^{-2\pi};e^{-2\pi}\right)_{\infty}^{4}}=\frac{\eta(4i)^2}{\eta(i)^4\eta(2i)^2}.$$

Indeed there are many ways to write this product, another I stumbled across is $$\frac{\left(-e^{-4\pi};e^{-4\pi}\right)_{\infty}^{2}}{\left(e^{-2\pi};e^{-2\pi}\right)_{\infty}^{4}}=\left(\frac{1}{\vartheta_{4}\left(e^{-4\pi}\right)\vartheta_{4}\left(e^{-2\pi}\right)}\right)^{2},$$ where $\vartheta_4(q)$ is a Jacobi theta function.

Answer by Eric Naslund for Density of a set of integers

2012-04-23T11:25:48Z

I just wanted to add, we also have a similar upper bound which combined with unknown(google)'s answer shows that

$$E_{r}(x)\asymp\frac{x\left(\log\log x\right)^{r}}{\left(\log x\right)^{\frac{1}{2}}}.$$

The above is almost certainly an asymptotic, and we can likely derive the explicit constant, but that would require a lot of calculation.

Upper bound: Let $\mathcal{A}=\left\{ n\in\mathbb{N}:\ p|n\Rightarrow p\equiv2\ (3)\right\}$ and let $\mathcal{B}=\left\{ n\in\mathbb{N}:\ p|n\Rightarrow p\equiv1\ (3)\right\}.$ Then

$$E_{r}(x)=\sum_{\begin{array}{c} n\leq x\ n\in\mathcal{A}\ \mu^{2}(n)=1,\omega(n)=r \end{array}}\sum_{\begin{array}{c} m\leq\frac{x}{n}\ m\in\mathcal{B}\ \mu(m)^{2}=1 \end{array}}1.$$

We then have the upper bound

$$E_{r}(x)\ll\sum_{\begin{array}{c} n\leq x\ \omega(n)=r \end{array}}\sum_{\begin{array}{c} m\leq\frac{x}{n}\ m\in\mathcal{B} \end{array}}1.$$

Carefully managing the sums, oone can then show that this is

$$\ll\frac{x}{\sqrt{\log x}}\sum_{\begin{array}{c} n\leq x\ \omega(n)=r \end{array}}\frac{1}{n}\ll\frac{x\left(\log\log x\right)^{r}}{\left(\log x\right)^{\frac{1}{2}}}. $$

Evaluating the integral $\int_{1}^{\infty}\frac{\{u\}}{u^{2}}\left(\log u\right)^{k}du.$

2011-05-11T01:26:13Z

I am trying to find a formula for the following integral for non-negative integer $k$:

$$\int_1^{\infty}\frac{\{u\}}{u^{2}}\left(\log u\right)^{k}du.$$

My first thought was to use the formula $$\zeta(s)-\frac{1}{s-1}=1-s\int_1^\infty u^{-s-1}\{u\}du$$ where $\{u\}$ refers to the fractional part. We can then take derivatives with respect to $s$ and use the Laurent expansion for $\zeta(s)$. It follows that each integral must be a finite linear combination of the Stieltjes Constants. All of the coefficients must be integers, and $\gamma_n$ can only appear if $n\leq k$. (This checks out numerically for $k=0,1,2$) Unfortunately, I am not sure what the pattern is, but I feel these particular integrals must be very common, and must have been dealt with before. I am hoping someone can give me a reference, or give a solution.

Thanks a lot,

Answer by Eric Naslund for Is the Cheeger constant of an induced subgraph of a cube at most 1?

2012-02-07T15:58:31Z

Your conjecture is true, every subgraph of the cube has expansion constant at most $1$.

Proof: Suppose we are given a subgraph $G\subset Q_n$, $n>1$ and cut the cube into $2$ $(n-1)$-dimensional subcubes $A_1,A_2$. (So that $A_1\cup A_2=Q_n$) The key is to notice that each vertex in $A_1$ is connected to one and only one vertex in $A_2$. Then split $G$ into two parts, $G_1=G\cap A_1$ and $G_2=G\cap A_2$. One of these will have size $\leq \frac{|G|}{2}$, suppose it is $G_1$. Because $G_1$ is in $A_1$, it is only connected to vertices in $A_2$, and we have $\partial G_1 \leq |G_1|$. Since the expansion constant is the minimum, we conclude that $$h(G)\leq 1.$$

Answer by Eric Naslund for Simplifying the expression involving instances of Gamma function

2012-01-03T08:45:57Z

I guess it depends on what you mean by simplify. We could rewrite things in terms of (generalized) central binomial coefficients:

First the denominator: Notice that $$\frac{\Gamma\left(1+\frac{1}{p}\right)^{2}}{\Gamma\left(1+\frac{2}{p}\right)}=\binom{\frac{2}{p}}{\frac{1}{p}}^{-1}=\frac{1}{2p}\frac{\Gamma\left(\frac{1}{p}\right)^{2}}{\Gamma\left(\frac{2}{p}\right)}.$$ For the numerator $$\frac{\Gamma\left(\frac{p+1}{2}\right)}{\Gamma\left(\frac{p+2}{2}\right)}=\frac{\Gamma\left(\frac{p+1}{2}\right)^{2}}{\Gamma\left(\frac{p+1}{2}+\frac{1}{2}\right)\Gamma\left(\frac{p+1}{2}\right)}=\frac{\Gamma\left(\frac{p+1}{2}\right)^{2}}{\sqrt{\pi}2^{-p}\Gamma\left(p+1\right)}=\frac{2^{p}}{p\sqrt{\pi}}\binom{p-1}{\frac{p-1}{2}}^{-1}$$ so the fraction becomes $$\frac{2^{p}}{p\sqrt{\pi}}\binom{\frac{2}{p}}{\frac{1}{p}}^{\frac{p+2}{2}}\biggr/\binom{p-1}{\frac{p-1}{2}}.$$ You could also write it using the beta function, then it is $$\frac{2^{\frac{3p+2}{2}}p^{\frac{p+2}{2}}}{\sqrt{\pi}}\frac{\text{B}\left(\frac{1}{p},\frac{1}{p}\right)^{\frac{p+2}{2}}}{\text{B}\left(\frac{p+1}{2},\frac{p+1}{2}\right)}.$$ To clean it up, it feels like you need a nicer way to write $\Gamma\left(\frac{1}{p}\right)^{p}$. It seems to look like a multinomial coefficient.

Now, there is a way to rewrite everything as a multidimensional integral over a simplex, and I find this to be the cleanest way to rewrite it. This is related to a generalization of the Beta Function. Tell me if this interests you, and I can include it.

Answer by Eric Naslund for averages of Euler-phi function and similar

2011-12-30T13:29:35Z

This exact question has actually been answered a few times on Math Stack Exchange.

See this for a general approach to finding the mean value of multiplicative functions which are "close" to $n$. Here is the idea:

Heuristic: Notice $f(n)\approx n$, then $\frac{f(n)}{n}\approx 1$. For functions close to one, convolution with the Möbius function will be close to zero, so we can deal with it easily. Lets define $g(n)=(\mu*\frac{f(d)}{d})(n)=\sum_{d|n}\frac{f(d)}{d}\mu\left(\frac{n}{d}\right)$ so that $(1*g)(n)=\frac{f(n)}{n}$. The idea will be to rewrite everything in terms of $g$ since $g(n)$ will be small.

The answer linked above provides the precise computation, and this will cover the Totient function, and the second example you gave above.

For the Totient function in particular, see this answer which also gives history of upper and lower bounds on the error term. In particular, the error term is surprisingly at least $\Omega (x\sqrt{\log \log x}).$

Hope that helps,

Answer by Eric Naslund for Every prime number > 19 divides one plus the product of two smaller primes?

2011-12-29T10:28:21Z

This answer is a heuristic along the lines of Joro's.

We use $p,q,r$ to denote primes. Let $S(p,a)$ denote the number of pairs of primes $(q,r)$ with $q,r\leq p$ and $p|(qr+a)$. We are interested in the case $a=1$, but in general by the orthogonality relations of the characters we have $$ S(p,a)=\frac{1}{\phi(p)}\sum_{r\leq p}\sum_{q\leq p}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\chi\left(qr\right).\ \ \ \ \ \ \ \ \ \ (1)$$ Rearranging this is $$S(p,a)=\frac{1}{p-1}\sum_{\chi\ \text{mod}\ p}\overline{\chi}(-a)\left(\sum_{q\leq p}\chi\left(q\right)\right)^{2}.$$

We might hope, as is the often the case, that the sums are all very small except when $\chi$ is principal, and that only the principal character contributes. With this in mind we expect

$$S(p,a)\approx \frac{1}{p} \text{li}(p)^2.$$

This is the same as conjecturing that $S(p,a)$ does not vary largely between $a$. In particular, if we average over all $a$ modulo $p$, then using (1) along with the orthogonality relation $\sum_{a\text{ mod } p}\sum_{\chi\text{ mod } p}\chi (a)=\phi(p)$, we see that $$\frac{1}{\phi(p)}\sum_{a\text{ mod } p} S(p,a)=\frac{1}{p-1}\sum_{r\leq p}\sum_{q\leq p}1=\frac{1}{p}\pi(p)^2\sim \frac{1}{p}\text{li}(p)^2.$$

Numerically this is remarkably close for $a=1$. Using the calculation done in Joro'sanswer, letting $a=1$ and $p=1000003$ we have $$S(p,1)=6184$$ whereas $$\frac{1}{p} \text{li}(p)^2=6182.307\dots $$

Now all that remains is to understand the sum $$\sum_{q\leq p}\chi\left(q\right)$$ for a character modulo $p$. However, I believe this is very difficult.

Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question.

2011-12-04T20:53:25Z

Apparently B6 of the Putnam this year asked:

Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ of the numbers $\sum^{p-1}_{k=0} k! n^{k}$ are not divisble by $p$.

With some rearrangements, this is equivalent to showing that $$E_p(z):=\sum_{k=0}^{p-1} \frac{z^k}{k!}$$ has at most $\frac{p-1}{2}$ zeros. A proof of this is at the end.

My question is: Can we improve the bound for the number of zeros? Also is there a deeper connection here with other parts of mathematics motivating this problem?

Proof of problem: Consider $$Q(z)=z^{p}-z+\sum_{l=0}^{p-1}\frac{z^{l}}{l!}.$$ Then for each integer $Q(n)=E(n).$ However, $$Q^{'}(z)\equiv E^{'}(z)-1=E(z)-\frac{z^{p-1}}{(p-1)!}-1\equiv E(z)+z^{p-1}-1.$$ Then, if $Q(n)=0$ for $n\neq0$ , we must also have $Q^{'}(n)=0$ so that $n$ is a double root of $Q(n).$ Since $\deg Q(n)=p$, we see that at most half of the integers $n\in\{ 1,2,\dots,p-1\}$ satisfy $E(n)=0.$ Since $E(0)=1$, we conclude the desired result.

Remark: This was asked in a slightly different form on math stack exchange. I felt the answer I posted there was inadequate there, and I personally became more curious while attempting to answer the question.

Comment by Eric Naslund

2013-04-18T17:44:37Z

This is an exact duplicate of: mathoverflow.net/questions/108912/…

Comment by Eric Naslund

2013-03-19T01:31:48Z

See the last part of this Math Stack Exchange answer: math.stackexchange.com/a/38142/6075

Comment by Eric Naslund

2013-03-18T18:33:54Z

At at a colloquium I once heard the comment, "Can we even prove that all the zeros of every primitive L-function are not all rational multiples of each other?"

Comment by Eric Naslund

2013-03-01T15:46:54Z

The question of irrationality is still open. See: en.wikipedia.org/wiki/…

Comment by Eric Naslund

2013-03-01T06:31:25Z

@Will Jagy: I didn't see the question on Math Stack Exchange until after answering this.

Comment by Eric Naslund

2013-03-01T06:31:01Z

When $l=0$ you obtain the result at the displayed equation in my answer above.

Comment by Eric Naslund

2013-02-19T18:15:45Z

@Stefan: I don't think you are normalizing correctly. Looking at the count of primes up to $3.206\cdot 10^{11}$, we expect the error term in the prime number race to be around $\sqrt{x}/\log x$, or in your case $$\sqrt{3.206*10^{11}}/\log(3.206*10^{11})\approx 21371.$$

Comment by Eric Naslund

2013-02-03T23:12:38Z

From the identity $$\prod_{i=1}^{2n}\left(1+\frac{1}{i}\right)^{(-1)^{i}}=\frac{(2n+1)!(2n)!}{2^{4n}n!^{4}},$$ along with Stirlings formula, you can determine that the infinite product converges to $\frac{2}{\pi}.$

Comment by Eric Naslund

2013-02-01T23:38:02Z

@Teo B: The movement in the negative and positive direction comes from the prime number race modulo $8$ between the residues $1$ and $5$. More often than not, there will be more primes congruent to $5$ modulo $8$ than $1$. (To be specific, we need to talk about the logarithmic density and assume GRH and LI) The first time that the primes congruent to $1$ modulo $8$ pulls ahead in the race is between $10^8$ and $10^9$.

Comment by Eric Naslund

2013-02-01T04:16:58Z

This may be more appropriate on academia.stackexchange.com

Comment by Eric Naslund

2013-01-20T18:28:15Z

How are the $x_1,\dots,x_n$ chosen? If they are all multiples of two, then the gcd condition never happens.

Comment by Eric Naslund

2013-01-08T02:03:17Z

This question is also partially answered by: mathoverflow.net/questions/32566/… and mathoverflow.net/questions/110057/…

Comment by Eric Naslund

2013-01-03T08:34:17Z

@Andy Putman: I don't think the OP claimed to have proved RH. His question is whether a particular statement is equivalent to RH.

Comment by Eric Naslund

2012-12-31T06:58:09Z

Can we even prove that there are infinitely many primes which in their decimal expansion do not contain the digit $9$?

Comment by Eric Naslund

2012-12-25T17:49:10Z

@quid: Thank you for your comments. I found the [paper](arxiv.org/abs/math/0609615), it is also by Goldston, Graham, Pintz and Yıldırım.