User eric naslund - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:44:39Z http://mathoverflow.net/feeds/user/12176 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/125250/recovering-sum-n-leq-x-an-from-sum-n-leq-x-ane-n-x/125543#125543 Answer by Eric Naslund for Recovering $\sum_{n \leq x} a(n)$ from $\sum_{n \leq x} a(n)e^{-n/x}$ Eric Naslund 2013-03-25T16:45:57Z 2013-03-25T16:45:57Z <p>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: </p> <p>$$\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)$$</p> <p>$$\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)$$ </p> <p>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.</p> http://mathoverflow.net/questions/71339/mathematical-advice-for-interested-highschool-students Mathematical Advice for Interested Highschool Students Eric Naslund 2011-07-26T18:36:22Z 2013-03-12T18:23:48Z <p>This may not be a research level math question, but I believe it is still relevant to Math Overflow. </p> <blockquote> <p>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?</p> </blockquote> <p>Thank you for your help,</p> http://mathoverflow.net/questions/52979/integer-points-on-the-elliptic-curve-y2x317 Integer Points on the Elliptic Curve $y^2=x^3+17$. Eric Naslund 2011-01-23T18:07:45Z 2013-03-12T00:49:14Z <p>I came across the problem "find all integer solutions to $y^2=x^3+17$." </p> <p>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)</p> <p>By numerical calculation I have found that the following integer points $(x,y)$ lie on the curve</p> <p>$(-1,4)$, $(-2,3)$, $(2,5)$, $(4,9)$, $(8,23)$, $(43,282)$, $(52,375)$, $(5234,378661)$ and this is probably all of them.</p> <p>Thanks</p> http://mathoverflow.net/questions/123290/how-to-rewrite-this-totient-summation-in-terms-of-mertens/123297#123297 Answer by Eric Naslund for How to rewrite this totient summation in terms of Mertens? Eric Naslund 2013-03-01T04:42:55Z 2013-03-01T04:42:55Z <p>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$$ </p> <p>$$=\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</p> <p>$$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</p> <p>$$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.$$ </p> http://mathoverflow.net/questions/54501/riemann-zeta-function-connection-to-quantum-mechanics Riemann Zeta Function connection to Quantum Mechanics. Eric Naslund 2011-02-06T06:36:36Z 2013-01-31T14:26:13Z <p>I feel like this question is probably wrong for MO, (too low level, perhaps unclear) but my curiosity has got the better of me:</p> <p>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:</p> <p>In theory, is it possible through physical experiments (particle experiments) to approximately calculate the first few zeros of the Riemann zeta function? </p> <p>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?</p> <p>(If there are conjectures/facts that we cannot prove, but would answer the question, I would be happy to hear those too)</p> <p>Thanks!</p> http://mathoverflow.net/questions/117191/using-quotient-of-prime-numbers-to-approximation-reals/117192#117192 Answer by Eric Naslund for Using Quotient of Prime Numbers to Approximation Reals Eric Naslund 2012-12-25T09:02:17Z 2012-12-25T17:50:05Z <p><strong>Question 1:</strong> The set is dense. </p> <p>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 <a href="http://www.cs.umd.edu/~gasarch/BLOGPAPERS/BakerHarmanPintz.pdf" rel="nofollow">the work</a> of Baker, Harman and Pintz on <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">prime gaps</a>. 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.$</p> <p><strong>Question 2:</strong> 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 <a href="http://en.wikipedia.org/wiki/Elliott%E2%80%93Halberstam_conjecture" rel="nofollow">Elliott-Halberstam Conjecture</a>, we can take $a\geq 6$.</p> <p>This is a corollary of <a href="http://arxiv.org/abs/math/0506067" rel="nofollow">the work</a> 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.</p> <p><strong>Edit:</strong> The <a href="http://arxiv.org/abs/math/0609615" rel="nofollow">more recent work</a> 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)</p> http://mathoverflow.net/questions/116336/combinatorial-interpretation-of-i-choose-n-where-i2-1/116346#116346 Answer by Eric Naslund for Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ Eric Naslund 2012-12-14T04:14:07Z 2012-12-15T23:41:19Z <p><strong>Asymptotics:</strong> Lets look at the quantity </p> <p><code>$$S(n)=(-1)^{n}(n+1)\binom{i}{n+1}=i\prod_{k=1}^{n+1}\left(1-\frac{i}{k}\right).$$</code> 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.</p> <blockquote> <p><strong>Claim:</strong> We have that </p> <p>$$S(n)=\sqrt{\frac{\sinh{\pi}}{\pi}}e^{iC_{0}}e^{-i\log n}\left(1+O\left(\frac{1}{n}\right)\right),$$ where</p> <p>$$C_{0}=\frac{-\pi}{2}-1+\int_0^\infty \frac{\{x\}}{1+x^2}dx =\arg(\Gamma(i))\approx -1.872.$$ </p> </blockquote> <p>In particular, the angle moves around the circle like $\log n$. </p> <p><strong>Application to your question:</strong> The above claim shows that <code>$$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)$$</code> and <code>$$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).$$</code> </p> <p>In particular, the ratio $g_n/f_n$ can be made arbitrarily large or small.</p> <p><em>Proof of the claim:</em> We first note that the size is</p> <p>$$\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</p> <p>$$-\sum_{k=1}^{n}\tan^{-1}\left(\frac{1}{k}\right).$$ </p> <p>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 </p> <p>$$\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.$$</p> <p>Pulling out the main term with the identity $[x]=x-\{x\}$, the above equals </p> <p>$$\int_{0}^{n}\frac{x}{1+x^{2}}dx-\int_{0}^{n}\frac{\{x\}}{1+x^{2}}dx.$$</p> <p>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).$$</p> <p><strong>Acknowledgements:</strong> 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.</p> <p><strong>Edit:</strong> 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).$$</p> http://mathoverflow.net/questions/85230/a-curious-limit-involving-prime-numbers-and-composite-numbers/85231#85231 Answer by Eric Naslund for A curious limit involving prime numbers and composite numbers Eric Naslund 2012-01-09T05:44:34Z 2012-12-03T01:35:56Z <p>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]$.</p> <p><strong>Remark:</strong> We need to use the fact that there exists $\theta&lt;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.$$</p> <p><strong>Edit:</strong> 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. </p> <p><strong>Edit 2:</strong> 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. </p> http://mathoverflow.net/questions/112735/there-are-two-points-on-the-earths-surface-that/112738#112738 Answer by Eric Naslund for There are two points on the Earth's surface that ... ? Eric Naslund 2012-11-18T01:49:10Z 2012-11-18T01:49:10Z <p>We can say the following:</p> <p>"At any given time, there are two points on the earth exactly 20 000 km apart with the same exact same temperature <em>and</em> barometric pressure."</p> <p>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 <a href="http://en.wikipedia.org/wiki/Borsuk%25E2%2580%2593Ulam_theorem" rel="nofollow">Wikipedia article</a> which you linked to in your question, we find the quote:</p> <p>"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."</p> http://mathoverflow.net/questions/97288/primes-with-more-ones-than-zeroes-in-their-binary-expansion/97345#97345 Answer by Eric Naslund for Primes with more ones than zeroes in their Binary expansion Eric Naslund 2012-05-18T19:20:41Z 2012-11-13T19:47:40Z <p>We can take $f(n)=\alpha n$ for any $\alpha&lt;0.7375$. In particular, the set of primes with more than twice as many ones that zeros in their binary expansion is infinite.</p> <p>I posted a short <a href="http://arxiv.org/abs/1211.2455" rel="nofollow">article on the arXiv</a> 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</p> <p>$$\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}}.$$</p> <p>Moreover, such a result extends naturally to base $q$, yielding the bound</p> <p>$$\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$.</p> <p>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.</p> <p><strong>Edit:</strong> At some point, I deleted my answer because I was unsatisfied with it. It has now been improved significantly.</p> http://mathoverflow.net/questions/96362/knight-tour-prime-conjecture/96366#96366 Answer by Eric Naslund for Knight tour prime (conjecture) Eric Naslund 2012-05-08T19:41:03Z 2012-11-13T19:17:55Z <p>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 <a href="http://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow">prime number theorem</a>, a corollary of the <a href="http://en.wikipedia.org/wiki/Selberg_sieve" rel="nofollow">Selberg sieve</a>, and a result concerning <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">prime gaps</a>.</p> <p><em>Proof:</em> We proceed by contradiction. </p> <p><strong>$n$ odd:</strong> 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.</p> <p><strong>$n$ even:</strong> 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 <em>must</em> be a jump to the second row, either two to the left, or two to the right. </p> <p><em>Key Idea:</em> 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 <code>$x&lt;n$</code>, the density of the primes in the interval <code>$[n+1,n+x]$</code> will be smaller then the density of the primes in <code>$[1,x]$</code>. Since <code>$[n+1,n+x]$</code> is in the second row, and <code>$[1,x]$</code> is in the first row, this contradicts the fact that the second row should have more primes.</p> <p>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.</p> <p><strong>Remark:</strong> We need only $$\pi(x+x^{\theta})-\pi(x)\sim \frac{x^\theta}{\log x}$$ for some $\theta&lt;1$, $\theta=\frac{7}{12}$ is much stronger than what is required.</p> <p><strong>Remark 2:</strong> 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.</p> <p><strong>Remark 3:</strong> It is quite likely that there is a clever elementary approach to solving the problem when $n$ is even.</p> http://mathoverflow.net/questions/111954/the-tightest-prime-zipper/111956#111956 Answer by Eric Naslund for The tightest prime zipper Eric Naslund 2012-11-10T01:14:03Z 2012-11-10T02:21:17Z <p>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. </p> <p><strong>Unconditional:</strong> 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}$. </p> <p><strong>Conditional:</strong> If we assume the <a href="http://en.wikipedia.org/wiki/Riemann_hypothesis" rel="nofollow">Riemann Hypothesis</a>, 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 <a href="http://en.wikipedia.org/wiki/Cram%25C3%25A9r%2527s_conjecture" rel="nofollow">Cramer's conjecture</a>, 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$.</p> <p>Also see this <a href="http://en.wikipedia.org/wiki/Prime_gap" rel="nofollow">Wikipedia article on prime gaps.</a></p> <p><strong>Remark:</strong> 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.</p> <p>** Avoid pointless functions such as $f(n)=p_n+1$.</p> http://mathoverflow.net/questions/32412/question-on-consecutive-integers-with-similar-prime-factorizations/111922#111922 Answer by Eric Naslund for Question on consecutive integers with similar prime factorizations Eric Naslund 2012-11-09T18:06:28Z 2012-11-09T18:14:36Z <p>This question is directly related to when $d(n)=d(n+1)$ where $d(n)$ denotes the divisor function.</p> <p><strong>Solutions to $d(n)=d(n+1)$:</strong></p> <p>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}.$$</p> <p>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}}.$$</p> <p>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.</p> <p><strong>Consecutive integers with identical prime signature:</strong></p> <p>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 <em>not</em> linear even though the graph resembles a straight line. ($\log \log x$ grows extremely slowly, and is nearly unnoticeable)</p> <p>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.</p> <p><strong>Some References:</strong> (Chronological Ordering)</p> <ul> <li><p>Erdös, Mirsky 1952: <a href="http://www.ams.org/mathscinet/search/publdoc.html?r=1&amp;pg1=CNO&amp;s1=49932&amp;loc=fromrevtext" rel="nofollow">The distribution of the values of $d(n)$.</a></p></li> <li><p>Heath-Brown 1984: <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=6990892" rel="nofollow">The divisor function at consecutive integers.</a></p></li> <li><p>Erdős, Pomerance and Sárközy 1987: <a href="http://www.jstor.org/stable/2046541?origin=crossref" rel="nofollow">On locally repeated values of certain arithmetic functions. III.</a> </p></li> <li><p>Hildebrand 1987: <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.pjm/1102690578" rel="nofollow">The divisor function at consecutive integers.</a></p></li> </ul> http://mathoverflow.net/questions/109561/an-application-of-mobius-inversion-in-a-paper-of-shintani/109568#109568 Answer by Eric Naslund for An application of Mobius Inversion in a paper of Shintani Eric Naslund 2012-10-13T23:37:06Z 2012-10-14T16:47:13Z <p>Let $g(n)$ denote the indicator function for the fourth powers. Then your sum equals </p> <p>$$\sum_{n\leq x}\left(h_{r}*g\right)(n),$$</p> <p>where $*$ denotes Dirichlet convolution. We may rewrite the given asymptotic as </p> <p>$$\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),$$</p> <p>noticing that this is of the form</p> <p>$$G(x)=\sum_{n\leq x}\alpha(n)F\left(\frac{x}{n}\right).$$</p> <p>Mobius inversion tells us that </p> <p>$$F(x)=\sum_{n\leq x}\alpha^{-1}(n)G\left(\frac{x}{n}\right),$$ </p> <p>where $\alpha^{-1}$ is the multiplicative inverse of $\alpha$ with respect to Dirichlet convolution. Applying Mobius inversion to our sum, we have that </p> <p>$$\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)$$</p> <p>which equals </p> <p>$$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)$$ </p> <p>$$=2^{-1}\zeta(2)x+O\left(x^{2/3+\epsilon}\right).$$ </p> <p>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.</p> http://mathoverflow.net/questions/109509/the-inverse-of-the-euler-totient-function/109511#109511 Answer by Eric Naslund for The Inverse of the Euler Totient Function Eric Naslund 2012-10-13T03:53:35Z 2012-10-13T04:03:41Z <p>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. </p> <p>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$.</p> <p>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}}.$$ </p> <p>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)$$</p> <p>For more details, see the following paper of Pomerance: <a href="http://www.math.dartmouth.edu/~carlp/popular.pdf" rel="nofollow">Popular Values of Euler's Function</a>.</p> http://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-n1-n/108939#108939 Answer by Eric Naslund for Number of elements in the set {1,...,n}*{1,..,n} Eric Naslund 2012-10-05T17:29:28Z 2012-10-06T04:48:44Z <p>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}.$$</p> <p>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)}.$$ </p> <p><strong>Some references:</strong></p> <ul> <li><p>Ford 2008: The distribution of integers with a divisor in a given interval. <a href="http://arxiv.org/abs/math/0401223" rel="nofollow">arXiv link</a></p></li> <li><p>Koukoulopoulos 2010: Localized Factorization of Integers. <a href="http://arxiv.org/abs/0809.1072" rel="nofollow">arXiv link</a></p></li> <li>Koukoulopoulos 2012: On the number of integers in a generalized multiplication table. <a href="http://arxiv.org/abs/1102.3236" rel="nofollow">arXiv link</a></li> </ul> <p><strong>Remark:</strong> The dates used above refer to the publication dates. (Not necessarily the date posted to the arXiv) </p> http://mathoverflow.net/questions/106278/problems-with-the-divisor-function-in-a-summation/106287#106287 Answer by Eric Naslund for Problems with the divisor function in a summation Eric Naslund 2012-09-04T00:21:40Z 2012-09-04T00:34:55Z <p>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$.</p> <p>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}.$$ </p> <p><strong>Added:</strong> 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.</p> <p>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$. </p> http://mathoverflow.net/questions/102720/better-error-bounds-for-partial-sums-of-reciprocals-of-primes/102723#102723 Answer by Eric Naslund for Better error bounds for partial sums of reciprocals of primes? Eric Naslund 2012-07-20T07:31:08Z 2012-07-25T19:21:37Z <p>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.</p> <p><em>Proof:</em> Let $W(x)=\pi(x)-\text{li}(x)$ be the error term in the prime number theorem. Then </p> <p>$$\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).$$ </p> <p>Integration by parts yields </p> <p><code>$$\int_{2}^{x}\frac{1}{t}dW(t)=\frac{W(t)}{t}\biggr|_{2}^{x}+\int_{2}^{x}\frac{W(t)}{t^{2}}dt.$$</code></p> <p>Since </p> <p>$$\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),$$ </p> <p>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),$$ </p> <p>where $b=\int_{2}^{\infty}\frac{\pi(t)-\text{li}(t)}{t^{2}}dt+\frac{W(2)}{2}-\log\log2.$ </p> http://mathoverflow.net/questions/101323/repeated-second-eigenvalue-of-the-adjacency-matrix-of-a-graph Repeated Second Eigenvalue of the Adjacency Matrix of a Graph Eric Naslund 2012-07-04T17:35:21Z 2012-07-04T21:24:37Z <p>This question is motivated by a talk I went to earlier today.</p> <p>Suppose we have a $d$-regular graph $G$ with $n$ vertices, with adjacency matrix $A$. </p> <p>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) </p> <p>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? </p> <p><strong>Additional questions:</strong> If $\lambda_1=\lambda_2=\cdots=\lambda_k&lt;\lambda_{k+1}$, then the graph will have exactly $k$ connected components. What can we say about $G$ if $\lambda_1&lt;\lambda_2=\cdots=\lambda_{k+1}&lt;\lambda_{k+2}$? That is, the second eigenvalue has multiplicity $k$.</p> <p>What if the $n^{th}$ eigenvalue has multiplicity $k$?</p> http://mathoverflow.net/questions/57395/median-largest-prime-factor/101222#101222 Answer by Eric Naslund for Median largest-prime-factor Eric Naslund 2012-07-03T08:41:47Z 2012-07-03T08:41:47Z <p>I posted <a href="http://arxiv.org/abs/1207.0232" rel="nofollow">a paper to the arXiv</a> which deals with this question along with some other things.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Euler%25E2%2580%2593Mascheroni_constant" rel="nofollow">Euler Mascheroni constant.</a></p> <p>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)$.) </p> <p>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),$$</p> <p>where $$c_k=1-\sum_{j=0}^k\frac{\gamma_k}{k!},$$ and $\gamma_k$ denotes the $k^{th}$ <a href="http://en.wikipedia.org/wiki/Stieltjes_constants" rel="nofollow">Stieltjes constant</a>.</p> http://mathoverflow.net/questions/82911/logarithmic-integral-of-nzeta-zeroes-and-certain-nested-sums-of-the-fractional-p/98908#98908 Answer by Eric Naslund for Logarithmic Integral of n^Zeta Zeroes and certain nested sums of the fractional part function Eric Naslund 2012-06-05T21:21:06Z 2012-06-05T22:12:34Z <p>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. </p> <p><strong>Notation:</strong> 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. </p> <p>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 </p> <p>$$\sum_{j=0}^{k}\binom{k}{j}(-1)^{j}D_{k-j}(n)=H_{k}(n) \ \ \ \ \ \ \ \ \ \ (2)$$</p> <p>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)$$</p> <p>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)$$</p> <p>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.$$ </p> <p>Removing the series expansion for the logarithm, this is </p> <p>$$=\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.</p> http://mathoverflow.net/questions/98862/an-equation-in-fractions/98866#98866 Answer by Eric Naslund for an equation in fractions Eric Naslund 2012-06-05T12:37:57Z 2012-06-05T12:43:38Z <p>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. </p> <p>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)}$.</p> <p>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.)</p> http://mathoverflow.net/questions/96223/q-pochhammer-symbol-identity/96249#96249 Answer by Eric Naslund for q-Pochhammer Symbol Identity Eric Naslund 2012-05-07T18:44:28Z 2012-05-12T12:24:09Z <p>The equality is indeed correct. It follows from identities in Ramanujan's notebook.</p> <p>First notice that <code>$\left(-1;e^{-4\pi}\right)_{\infty}^{2}=2\left(-e^{-4\pi};e^{-4\pi}\right)_{\infty}^{2},$</code> so we are trying to prove the identity</p> <p><code>$$\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)}.$$</code></p> <p>The right hand side many be cleaned up further, and written as </p> <p><code>$$\frac{32\pi^{3}2^{\frac{1}{8}}\sqrt{\sqrt{2}-1}}{\Gamma^{4}\left(\frac{1}{4}\right)}.$$</code> </p> <p>Now, since <code>$1+q^{4}=\frac{1-q^{8}}{1-q^{4}},$</code> the left hand side is</p> <p><code>$$\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)$$</code> </p> <p>On page 326 of Bruce C Brendts “Ramanujan's Notebook Part V” he shows that</p> <p><code>$$\left(e^{-2\pi}\right)_{\infty}=\frac{\Gamma\left(\frac{1}{4}\right)}{2\pi^{\frac{3}{4}}}e^{\frac{\pi}{12}}$$</code></p> <p><code>$$\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}}$$</code> and </p> <p><code>$$\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}}.$$</code></p> <p>Combining these three together in equation (1) yields the desired result.</p> <p><strong>Remark:</strong> You could have proceeded in a different manner by noticing that the denominator is (almost) the <a href="http://mathworld.wolfram.com/DedekindEtaFunction.html" rel="nofollow">Dedkind eta function</a>. The product can be written as </p> <p><code>$$\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}.$$</code> </p> <p>Indeed there are many ways to write this product, another I stumbled across is <code>$$\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},$$</code> where <code>$\vartheta_4(q)$</code> is a <a href="http://mathworld.wolfram.com/JacobiThetaFunctions.html" rel="nofollow">Jacobi theta function.</a></p> http://mathoverflow.net/questions/94543/density-of-a-set-of-integers/94927#94927 Answer by Eric Naslund for Density of a set of integers Eric Naslund 2012-04-23T11:25:48Z 2012-04-23T11:25:48Z <p>I just wanted to add, we also have a similar upper bound which combined with unknown(google)'s answer shows that </p> <p>$$E_{r}(x)\asymp\frac{x\left(\log\log x\right)^{r}}{\left(\log x\right)^{\frac{1}{2}}}.$$</p> <p>The above is almost certainly an asymptotic, and we can likely derive the explicit constant, but that would require a lot of calculation.</p> <p><strong>Upper bound:</strong> 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 </p> <p>$$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.$$ </p> <p>We then have the upper bound</p> <p>$$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.$$ </p> <p>Carefully managing the sums, oone can then show that this is </p> <p>$$\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}}}.$$</p> http://mathoverflow.net/questions/64556/evaluating-the-integral-int-1-infty-frac-u-u2-left-log-u-right Evaluating the integral $\int_{1}^{\infty}\frac{\{u\}}{u^{2}}\left(\log u\right)^{k}du.$ Eric Naslund 2011-05-11T01:26:13Z 2012-04-16T11:41:08Z <p>I am trying to find a formula for the following integral for non-negative integer $k$: </p> <p><code>$$\int_1^{\infty}\frac{\{u\}}{u^{2}}\left(\log u\right)^{k}du.$$</code></p> <p>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 <a href="http://en.wikipedia.org/wiki/Stieltjes_constants" rel="nofollow">Stieltjes Constants</a>. 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.</p> <p>Thanks a lot,</p> http://mathoverflow.net/questions/87730/is-the-cheeger-constant-of-an-induced-subgraph-of-a-cube-at-most-1/87808#87808 Answer by Eric Naslund for Is the Cheeger constant of an induced subgraph of a cube at most 1? Eric Naslund 2012-02-07T15:58:31Z 2012-02-08T11:02:29Z <p>Your conjecture is true, every subgraph of the cube has expansion constant at most $1$.</p> <p><em>Proof:</em> 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.$$ </p> http://mathoverflow.net/questions/82745/simplifying-the-expression-involving-instances-of-gamma-function/84791#84791 Answer by Eric Naslund for Simplifying the expression involving instances of Gamma function Eric Naslund 2012-01-03T08:45:57Z 2012-01-03T08:45:57Z <p>I guess it depends on what you mean by simplify. We could rewrite things in terms of (generalized) central binomial coefficients:</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/84571/averages-of-euler-phi-function-and-similar/84588#84588 Answer by Eric Naslund for averages of Euler-phi function and similar Eric Naslund 2011-12-30T13:29:35Z 2011-12-30T19:10:44Z <p>This exact question has actually been answered a few times on Math Stack Exchange.</p> <p><a href="http://math.stackexchange.com/a/90125/6075" rel="nofollow">See this</a> for a general approach to finding the mean value of multiplicative functions which are "close" to $n$. Here is the idea:</p> <p><strong>Heuristic:</strong> 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.</p> <p>The answer linked above provides the precise computation, and this will cover the Totient function, and the second example you gave above. </p> <p>For the Totient function in particular, <a href="http://math.stackexchange.com/questions/37863/asymptotic-formula-for-munx-n2-summation/38142#38142" rel="nofollow">see this answer</a> 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}).$</p> <p>Hope that helps,</p> http://mathoverflow.net/questions/84374/every-prime-number-19-divides-one-plus-the-product-of-two-smaller-primes/84501#84501 Answer by Eric Naslund for Every prime number > 19 divides one plus the product of two smaller primes? Eric Naslund 2011-12-29T10:28:21Z 2011-12-29T17:00:47Z <p>This answer is a <strong>heuristic</strong> along the lines of Joro's.</p> <p>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}.$$</p> <p>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</p> <p>$$S(p,a)\approx \frac{1}{p} \text{li}(p)^2.$$ </p> <p>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.$$ </p> <p>Numerically this is <strong>remarkably</strong> 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$$</p> <p>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. </p> http://mathoverflow.net/questions/82648/truncated-exponential-series-modulo-p-deeper-meaning-for-a-putnam-question Truncated Exponential Series Modulo $p$: Deeper meaning for a Putnam Question. Eric Naslund 2011-12-04T20:53:25Z 2011-12-20T23:31:31Z <p><a href="http://math.stackexchange.com/questions/88188/asking-2011-putnam-b6" rel="nofollow">Apparently B6 of the Putnam</a> this year asked:</p> <blockquote> <p>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$. </p> </blockquote> <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.</p> <p><strong>My question is:</strong> 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?</p> <blockquote> <p>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.</p> </blockquote> <p><strong>Remark:</strong> This was asked in a slightly different form on <a href="http://math.stackexchange.com/questions/88188/asking-2011-putnam-b6" rel="nofollow">math stack exchange</a>. I felt the answer I posted there was inadequate there, and I personally became more curious while attempting to answer the question.</p> http://mathoverflow.net/questions/127991/estimates-for-the-size-of-the-product-set-n-n Comment by Eric Naslund Eric Naslund 2013-04-18T17:44:37Z 2013-04-18T17:44:37Z This is an exact duplicate of: <a href="http://mathoverflow.net/questions/108912/number-of-elements-in-the-set-1-n1-n/108939#108939" rel="nofollow" title="number of elements in the set 1 n1 n">mathoverflow.net/questions/108912/&hellip;</a> http://mathoverflow.net/questions/124889/probability-that-two-random-integers-are-coprime Comment by Eric Naslund Eric Naslund 2013-03-19T01:31:48Z 2013-03-19T01:31:48Z See the last part of this Math Stack Exchange answer: <a href="http://math.stackexchange.com/a/38142/6075" rel="nofollow">math.stackexchange.com/a/38142/6075</a> http://mathoverflow.net/questions/124572/is-there-an-explicit-expression-for-the-imaginary-part-of-some-non-trivial-zero-o/124885#124885 Comment by Eric Naslund Eric Naslund 2013-03-18T18:33:54Z 2013-03-18T18:33:54Z At at a colloquium I once heard the comment, &quot;Can we even prove that all the zeros of every primitive L-function are not <i>all</i> rational multiples of each other?&quot; http://mathoverflow.net/questions/123343/euler-constant-transcendality Comment by Eric Naslund Eric Naslund 2013-03-01T15:46:54Z 2013-03-01T15:46:54Z The question of irrationality is still open. See: <a href="http://en.wikipedia.org/wiki/Euler%E2%80%93Mascheroni_constant#Properties" rel="nofollow">en.wikipedia.org/wiki/&hellip;</a> http://mathoverflow.net/questions/123290/how-to-rewrite-this-totient-summation-in-terms-of-mertens/123297#123297 Comment by Eric Naslund Eric Naslund 2013-03-01T06:31:25Z 2013-03-01T06:31:25Z @Will Jagy: I didn't see the question on Math Stack Exchange until after answering this. http://mathoverflow.net/questions/123290/how-to-rewrite-this-totient-summation-in-terms-of-mertens/123297#123297 Comment by Eric Naslund Eric Naslund 2013-03-01T06:31:01Z 2013-03-01T06:31:01Z When $l=0$ you obtain the result at the displayed equation in my answer above. http://mathoverflow.net/questions/120552/prime-race-in-2-dimensions Comment by Eric Naslund Eric Naslund 2013-02-19T18:15:45Z 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.$$ http://mathoverflow.net/questions/120712/estimate-the-infinite-product Comment by Eric Naslund Eric Naslund 2013-02-03T23:12:38Z 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}.$ http://mathoverflow.net/questions/120552/prime-race-in-2-dimensions Comment by Eric Naslund Eric Naslund 2013-02-01T23:38:02Z 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$. http://mathoverflow.net/questions/120486/should-i-tell-my-coauthor Comment by Eric Naslund Eric Naslund 2013-02-01T04:16:58Z 2013-02-01T04:16:58Z This may be more appropriate on <a href="http://academia.stackexchange.com/" rel="nofollow">academia.stackexchange.com</a> http://mathoverflow.net/questions/119416/probability-of-all-combinations-of-k-numbers-among-n-being-coprime Comment by Eric Naslund Eric Naslund 2013-01-20T18:28:15Z 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. http://mathoverflow.net/questions/118320/leaving-academia Comment by Eric Naslund Eric Naslund 2013-01-08T02:03:17Z 2013-01-08T02:03:17Z This question is also partially answered by: <a href="http://mathoverflow.net/questions/32566/careers-advice-for-ph-d-s-without-current-postdocs-or-university-jobs/32584#32584" rel="nofollow" title="careers advice for ph d s without current postdocs or university jobs">mathoverflow.net/questions/32566/&hellip;</a> and <a href="http://mathoverflow.net/questions/110057/lost-soul-loneliness-in-pursing-math-advice-needed-closed" rel="nofollow" title="lost soul loneliness in pursing math advice needed closed">mathoverflow.net/questions/110057/&hellip;</a> http://mathoverflow.net/questions/117874/a-closed-form-of-infinite-products-of-complex-zeros-involving-im-rho-n-does Comment by Eric Naslund Eric Naslund 2013-01-03T08:34:17Z 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. http://mathoverflow.net/questions/117689/3-7-primes-in-base-10 Comment by Eric Naslund Eric Naslund 2012-12-31T06:58:09Z 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$? http://mathoverflow.net/questions/117191/using-quotient-of-prime-numbers-to-approximation-reals/117192#117192 Comment by Eric Naslund Eric Naslund 2012-12-25T17:49:10Z 2012-12-25T17:49:10Z @quid: Thank you for your comments. I found the [paper](<a href="http://arxiv.org/abs/math/0609615" rel="nofollow">arxiv.org/abs/math/0609615</a>), it is also by Goldston, Graham, Pintz and Yıldırım.