User charles - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T23:41:22Z http://mathoverflow.net/feeds/user/6043 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/33045/product-over-the-primes Product over the primes Charles 2010-07-23T05:12:47Z 2013-04-13T09:18:37Z <p>I'm trying to estimate the product $$\prod_{p\lt q\lt r\lt s}1-\frac{24}{(pqrs)^2}$$ where $p,q,r,s$ are primes.</p> <p>This is for the purpose of calculating the density of Sloane's A070284 [1]. The idea is that there are 4! congruence classes mod $(pqrs)^2$ such that $n,n+1,n+2,n+3$ are each congruent to 0 mod the square of one of the primes. A number is not the first of four such numbers exactly when it is not in any of these congruence classes for any quadruple of distinct primes.</p> <p>I feel that there should be some way to accelerate the calculation, possibly using the prime zeta function. At the least, this is useful for the sum approximation which is far easier to calculate with dynamic programming (making it essentially linear rather than quartic, if you can spare $O(n)$ memory). Unfortunately there are enough congruence classes that the cancellation is an important part of the problem, so the sum approximation is poor.</p> <p>Any suggestions for the calculation, or different approaches to the problem, would be appreciated.</p> <p>[1] <a href="http://oeis.org/classic/A070284" rel="nofollow">http://oeis.org/classic/A070284</a></p> http://mathoverflow.net/questions/127248/at-what-point-would-an-elementary-generalization-of-bertrands-postulate-be-inter/127252#127252 Answer by Charles for At what point would an elementary generalization of Bertrand's Postulate be interesting? Charles 2013-04-11T14:31:21Z 2013-04-11T14:31:21Z <p>I think that it would be interesting if it has an effective (and not too huge) value of $X$.</p> http://mathoverflow.net/questions/35927/asymptotic-density-of-k-almost-primes Asymptotic density of k-almost primes Charles 2010-08-18T04:37:54Z 2013-01-08T21:24:51Z <p>Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the <em>k</em>-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is $$\pi_k(x)\sim\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\qquad\qquad(1)$$ but this approximation is very poor for $k>1$.</p> <p>For $\pi(x)$ much more is known. A (divergent) asymptotic series $$\pi(x)=\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{\log^2x}+\frac{6}{\log^3x}\cdots\right)\qquad\qquad(2)$$ exists (see. e.g., the historical paper of Cipolla [1] who inverted this to produce a series for $p_n$). And of course it is well-known that $$\pi(x)=\operatorname{Li}(x)+e(x)\qquad\qquad(3)$$ for an error term $e(x)$ (not sure what the best current result) that can be taken [4], on the RH, to be $O(\sqrt x\log x)$. Even better, Schoenfeld [6] famously transformed this into an effective version with $$|e(x)|&lt;\sqrt x\log x/8\pi\qquad\qquad(4)$$ for $x\ge2657$. For the heretics who are not certain of the Riemann Hypothesis, Pierre Dusart has a preprint [2] which improves on the results in his thesis [3]; in particular, for $x\ge2953652302$, $$\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2}{\log^2x}\right)\le\pi(x)\le\frac{x}{\log x}\left(1+\frac{1}{\log x}+\frac{2.334}{\log^2x}\right)\qquad\qquad(5)$$</p> <p>But I know of no results even as weak as (2) for almost primes. Even if nothing effective like (5) exists, I would be happy for an estimate like (3).</p> <h2>Partial results</h2> <p>Montgomery &amp; Vaughan [5] show that $$\pi_k=G\left(\frac{k-1}{\log\log x}\right)\frac{x(\log\log x)^{k-1}}{(k-1)!\log x}\left(1+O\left(\frac{k}{(\log\log x)^2}\right)\right)$$ for any fixed k (and, indeed, uniformly for any $1\le k\le(2-\varepsilon)\log\log x$ though the O depends (exponentially?) on the $\varepsilon$), where $$G(z)=F(1,z)/\Gamma(z+1)$$ and $$F(s,z)=\prod_p\left(1-\frac{z}{p^s}\right)^{-1}\left(1-\frac{1}{p^s}\right)^z$$ though I'm not quite sure how to calculate $F$.</p> <p>If this is the best result known (rather than simply the best result provable at textbook level) then this shows that far less is known about the distribution of, e.g., semiprimes than about primes.</p> <h2>References</h2> <p>[1] M. Cipolla, “La determinazione assintotica dell n$^\mathrm{imo}$ numero primo”, <em>Matematiche Napoli</em> <strong>3</strong> (1902), pp. 132-166.</p> <p>[2] Pierre Dusart, "Estimates of Some Functions Over Primes without R.H." (2010) <a href="http://arxiv.org/abs/1002.0442" rel="nofollow">http://arxiv.org/abs/1002.0442</a></p> <p>[3] Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers" (1998) <a href="http://www.unilim.fr/laco/theses/1998/T1998_01.html" rel="nofollow">http://www.unilim.fr/laco/theses/1998/T1998_01.html</a></p> <p>[4] Helge von Koch, "Sur la distribution des nombres premiers". <em>Acta Mathematica</em> <strong>24</strong>:1 (1901), pp. 159-182.</p> <p>[5] Hugh Montgomery &amp; Robert Vaughan, Multiplicative Number Theory I. Classical Theory. (2007). Cambridge University Press.</p> <p>[6] Lowell Schoenfeld, "Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x). II". <em>Mathematics of Computation</em> <strong>30</strong>:134 (1976), pp. 337-360.</p> <p>[7] Robert G. Wilson v, Number of semiprimes &lt;= 2^n. In Sloane's On-Line Encyclopedia of Integer Sequences, A125527. <a href="http://oeis.org/classic/A125527" rel="nofollow">http://oeis.org/classic/A125527</a> ; c.f. <a href="http://oeis.org/classic/A007053" rel="nofollow">http://oeis.org/classic/A007053</a></p> http://mathoverflow.net/questions/116048/maximum-size-of-powers-with-a-given-difference Maximum size of powers with a given difference Charles 2012-12-11T06:01:38Z 2012-12-12T02:38:55Z <p>Pillai's conjecture -- that the gap between (nontrivial) powers is unbounded below -- is still open (it would be a consequence of the $abc$ conjecture, were that proven). But I wonder what the right order of magnitude for it is, even though a proof seems far off.</p> <p>Suppose $n=|a^x-b^y|$ for integers $a,b,x,y$ with $a,b\ge1$ and $x,y\ge2.$ What is the (conjectural) maximal order of $a^x$?</p> <p>$17 = 378661^2 - 5234^3$ so we should not expect it to be too tiny. But I don't even know if the right order should be polynomial, exponential, doubly-exponential, etc. Does anyone have insight here?</p> http://mathoverflow.net/questions/114496/proving-a-least-prime-factor Proving a least prime factor Charles 2012-11-26T07:52:13Z 2012-11-26T13:43:37Z <p>Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide $n/p$ by all the primes below $p$ (ideally with a Bernstein remainder tree).</p> <p>But sometimes neither approach is practical, say if $p\approx10^{20}$ and $n\approx10^{200}$. Is there a method for determining whether $p$ is the smallest prime factor of $n$ or, equivalently, whether $n/p$ has any prime factors less than $p$, faster than either of the naive methods above?</p> <p>Of course this is (fairly) easy to determine with high probability: run an appropriate number of ECM curves. But can this be done deterministically?</p> http://mathoverflow.net/questions/48461/analytic-lower-bounds-on-the-first-sign-change-of-pix-lix Analytic lower bounds on the first sign change of pi(x) - li(x)? Charles 2010-12-06T17:37:03Z 2012-11-11T10:42:17Z <p>There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays &amp; Hudson, Demichael, Chao &amp; Plymen, and most recently Saouter &amp; Demichel. These provide upper bounds (as well as lower bounds on some region in which $\pi(x)>{\mathrm{li}}(x)$).</p> <p>Could these methods be used to generate a lower bound? That is, a region [2, y] in which $\pi(x)&lt;{\mathrm{li}}(x)$. (Or even a region [x, y] where y is smaller than the best known upper bound, such that, in principle at least, direct calculations could yield a lower bound.)</p> <p>It seems unlikely that direct searches like [2] will ever be able to resolve the exact value of the first crossing.</p> <hr> <p>[1] C. Bays and R. H. Hudson. "<a href="http://www.ams.org/journals/mcom/2000-69-231/S0025-5718-99-01104-7/" rel="nofollow">A new bound for the smallest x with $\pi(x)>{\mathrm{li}}(x)$</a>" <em>Mathematics of Computation</em> <strong>69</strong> (2000), pp. 1285–1296.</p> <p>[2] T. Kotnik. "<a href="http://lbk.fe.uni-lj.si/pdfs/aicm2008.pdf" rel="nofollow">The prime-counting function and its analytic approximations</a>", <em>Advances in Computational Mathematics</em> <strong>29</strong> (2008), pp. 55-70.</p> <p>[2] R. Sherman Lehman. "<a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa11/aa11132.pdf" rel="nofollow">On the difference $\pi(x)-{\mathrm{li}}(x)$</a>" <em>Acta Arithmetica</em> <strong>11</strong> (1965), pp. 397–410.</p> <p>[3] H. J. J. te Riele. "<a href="http://www.ams.org/mcom/1987-48-177/S0025-5718-1987-0866118-6/S0025-5718-1987-0866118-6.pdf" rel="nofollow">On the sign of the difference $\pi(x)-{\mathrm{li}}(x)$</a>" <em>Mathematics of Computation</em> <strong>48</strong> (1987), pp. 323–328.</p> <p>[4] Yannick Saouter and Patrick Demichel. "<a href="http://www.ams.org/journals/mcom/2010-79-272/S0025-5718-10-02351-3/home.html" rel="nofollow">A sharp region where $\pi(x)-{\mathrm{li}}(x)$ is positive</a>" <em>Mathematics of Computation</em> <strong>79</strong> (2010), pp. 2395-2405.</p> http://mathoverflow.net/questions/42393/has-stirlings-formula-ever-been-applied-with-interesting-consequence-to-wilson/42398#42398 Answer by Charles for Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem? Charles 2010-10-16T18:46:35Z 2012-10-03T19:53:32Z <p>Using Robbins' [1] form of Stirling's formula,</p> <p>$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))&lt; n!&lt; \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$</p> <p>we get</p> <p>$$\left\lceil\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-11))\right\rceil$$ $$\le (n-1)!\le$$ $$\left\lfloor\sqrt{2\pi}(n-1)^{n-1/2}\exp(-n-1+1/(12n-12))\right\rfloor$$</p> <p>which is accurate enough to distinguish prime from composite for $n\le8$. For larger numbers, the error bound is too large.</p> <hr> <p>This can be extended further using a modification of Wilson's theorem: for n > 9, $$\lfloor n/2\rfloor!\equiv0\pmod n$$ if and only if n is composite. This allows testing 10 through 15, plus (with some cleverness) 17.</p> <p>With tighter explicit bounds and high-precision evaluation, it might be possible to test as high as 100 with related methods: direct evaluation up to 25 and the 'divide by 4' variant of the above for n > 25.</p> <p>This is not so much 'using a cannon to swat a fly' (using methods more powerful than needed) as it is 'using the space station to swat a fly': the methods must be extremely powerful and accurate to do very little.</p> <hr> <p>[1] H. Robbins, "A Remark on Stirling's Formula." <em>The American Mathematical Monthly</em> <strong>62</strong> (1955), pp. 26-29.</p> http://mathoverflow.net/questions/106682/large-gaps-between-p2s Large gaps between P2s Charles 2012-09-08T19:14:11Z 2012-09-08T22:29:46Z <p>Gaps between consecutive primes are $O(n^{\theta+\varepsilon})$ for $\theta=0.525$ and any $\varepsilon>0.$ I was wondering if a better result is known for gaps between numbers with at most two prime factors. (It seems that this would be easier because it removes the parity obstacle.)</p> <p>I am interested in both unconditional results and those conditional on standard hypotheses.</p> <p>Related result: Harman (1981) showed that almost all intervals of length $(\log x)^{7+\varepsilon}$ contains a $P_2.$</p> http://mathoverflow.net/questions/84989/upper-bounds-on-the-difference-of-consecutive-zeta-zeros Upper bounds on the difference of consecutive zeta zeros Charles 2012-01-05T18:54:00Z 2012-08-07T18:22:34Z <p>There are many results on the spacing of the gaps between nontrivial zeros of the $\zeta$ function, from trivial (average value is $\frac{2\pi}{\log\gamma_n}$) to difficult (bounds on max and min values of the normalized gap). Are any reasonable upper bounds known? I'd like to have something that says, given any $\varepsilon>0,$ there is some N beyond which the gaps $\gamma_{n+1}-\gamma_n$ is at most $\varepsilon.$ This seems a weak request given the asymptotic behavior but I haven't found anything along these lines.</p> <p>Any ideas?</p> <p>I <a href="http://math.stackexchange.com/q/95693/1778" rel="nofollow">asked the question on math.se</a> but did not get an answer.</p> http://mathoverflow.net/questions/103111/prescribed-values-for-the-uniform-density Prescribed values for the uniform density Charles 2012-07-25T17:10:46Z 2012-07-25T23:18:42Z <p>Strauch &amp; Tóth [1] showed that for any choice of upper and lower density, there is some subset of $\mathbb{N}$ with the chosen densities, provided the lower is no more than the upper and both are in [0, 1].</p> <p>Mišík [2] extended this to show that for any choice of upper density, lower density, upper logarithmic density, and lower logarithmic density there is a subset of $\mathbb{N}$ with the chosen densities, provided they follow the necessary inequalities $0\le\underline d\le\underline\delta\le\overline d\le\overline\delta\le1.$</p> <p>Is there a similar result with the uniform densities? $$\underline{u}(A)=\lim_s\frac1s\liminf_n\sum_\stackrel{a\in A}{\ n &lt; a\le n+s}1$$ $$\overline{u}(A)=\lim_s\frac1s\limsup_n\sum_\stackrel{a\in A}{\ n &lt; a\le n+s}1$$</p> <p>An ideal result would combine all three density types with the inequality $$0\le\underline{u}\le\underline{d}\le\underline{\delta}\le\overline{\delta}\le\overline{d}\le\overline{u}\le1$$ but I'm looking for any published results on the topic.</p> <p>[1] Strauch and Tóth, Asymptotic density of $A\subset N$ and density of the ratio set $R(A)$. <em>Acta Arith.</em> <strong>87</strong> (1998), pp. 67-78.</p> <p>[2] Ladislav Mišík, Sets of positive integers with prescribed values of densities, <em>Mathematica Slovaca</em> <strong>52</strong>:3 (2002), pp. 289-296.</p> http://mathoverflow.net/questions/103014/lacunary-sequence Lacunary sequence Charles 2012-07-24T15:38:18Z 2012-07-25T01:52:39Z <p>Is there a standard definition for a lacunary sequence?</p> <p>Suppose $0 &lt; a_1 &lt; a_2 &lt; \cdots.$</p> <p>I've read two papers using the term recently. One requires $$\liminf_n\frac{a_{n+1}}{a_n}>1$$ while the other only requires $$\lim_na_{n+1}-a_n=+\infty.$$</p> <p>The two differ, of course: $a_1=1,\ a_{n+1}=a_n+\sqrt{a_n}$ has a ratio that tends to 1 but a difference that diverges.</p> <p>Further, the <a href="http://www.encyclopediaofmath.org/index.php/Lacunary_sequence" rel="nofollow">EOM entry for lacunary sequence</a> is different from both (a finite form of the first): $$\frac{a_{n+1}}{a_n}\ge\lambda>1.$$</p> http://mathoverflow.net/questions/102540/product-of-fibonacci-numbers Product of Fibonacci numbers Charles 2012-07-18T13:36:30Z 2012-07-18T23:52:40Z <p>Consider the counting function $$f(x)=|\{n\le x:n\text{ is a product of Fibonacci numbers}\}|$$ so for example $f(4)=4=|\{1,2,3,4\}|$ since 1, 2, and 3 are Fibonacci numbers and $4=F_3\cdot F_3.$ (See <a href="https://oeis.org/A065108" rel="nofollow">A065108</a>.)</p> <p>What is known, asymptotically, about the growth of $f$?</p> <p>It's clear that for any $k$, $f(x)\gg(\log x)^k$ (this can be made effective without too much work), and it doesn't seem likely that $f(x)\gg x^k$ for any $k>0$.</p> http://mathoverflow.net/questions/100027/sum-of-the-sum-of-divisors-function Sum of the sum-of-divisors function Charles 2012-06-19T18:00:33Z 2012-06-24T14:14:27Z <p>I was looking at <a href="http://rd.springer.com/article/10.1007/BF01630684" rel="nofollow">the abstract</a> of a paper [1] which claims that [2] and [3] prove $$\sum_{n\le x}\sigma(n)-\frac{\pi^2}{12}x^2=\Omega(x\log\log x).$$</p> <p>But I cannot find the above&mdash;or indeed, anything approaching it&mdash;in [2]. Have I missed something?</p> <p>The paper [3] clearly discusses the appropriate function and presumably gives the indicated result. I must decipher its notation, though: the author seems to use $\sigma(n)$ to denote what would usually be written $\sigma_{-1}(n)=\sigma(n)/n.$</p> <h2>References</h2> <p>[1] Y.-F. S. Pétermann, "An Ω-theorem for an error term related to the sum-of-divisors function", <em>Monatshefte für Mathematik</em> 103:2 (1987), pp. 145-157.</p> <p>[2] T. H. Gronwall, "Some asymptotic expressions in the theory of numbers", <em>Trans. Amer. Math. Soc.</em> <strong>14</strong> (1913), pp. 113–122. <a href="http://www.jstor.org/stable/1988773" rel="nofollow">JSTOR</a></p> <p>[3] S. Wigert, <a href="http://home.us.archive.org/stream/actamathematica37upps#page/n145/mode/2up" rel="nofollow">Sur quelques fonctions arithmétiques</a>, <em>Acta Math.</em> <strong>37</strong> (1914), pp. 113–140.</p> http://mathoverflow.net/questions/100265/not-especially-famous-long-open-problems-which-anyone-can-understand/100274#100274 Answer by Charles for Not especially famous, long-open problems which anyone can understand Charles 2012-06-21T19:15:02Z 2012-06-21T19:15:02Z <p>A meta-answer: I recommend Guy's <em>Unsolved Problems in Number Theory</em> and perhaps some of his others (<em>Unsolved Problems in Geometry</em>, <em>Unsolved Problems in Combinatorial Games</em>), which have many unsolved problems (both well-known and obscure), grouped into categories. Many of these are of attackable difficulty.</p> http://mathoverflow.net/questions/95726/mertens-function-in-time-o-sqrt-x Mertens' function in time $O(\sqrt x)$ Charles 2012-05-02T05:38:57Z 2012-05-10T21:13:50Z <p><a href="http://mathoverflow.net/questions/36358/computing-the-mertens-function" rel="nofollow">This MathOverflow question</a> seems to indicate that the state of the art in computing $$M(x)=\sum_{n\le x}\mu(n)$$ takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. Recently I came across a paper [1] which gives, almost as an afterthought, an algorithm for computing $M(x)$ in $O(\sqrt x)$ time (in section 3.2).</p> <p>The algorithm itself seems to be correct, being derived in a straightforward way from the identity $$M(x)=1-\sum_{d\ge2}M(x/d).$$ But the claim that is runs in time $O(\sqrt x),$ or even $O(x^{1/2+\varepsilon}),$ seems unusual enough for me to ask for verification.</p> <p>First, this would be a major breakthrough in computing $M(x),$ enough that I would think it would merit more mention than a substep of another algorithm. At the least, I would expect a mention that previous algorithms were slower.</p> <p>Second, the algorithm is very simple, so that if the time is as indicated the implied constant should be low and the algorithm should be practical. In any case it is not hard to program.</p> <p>Third, on coding the algorithm I found it to be very slow. In fact, it was slower for those values tested than <code>sum(n=1, 10^7, moebius(n))</code> in <a href="http://pari.math.u-bordeaux.fr/" rel="nofollow">GP</a> which involves factoring each number up to $10^7.$ The time needed to factor numbers of those sizes is about $\sqrt x/\log x$ on average, so that's a $\Theta(n^{3/2}/\log n)$ algorithm (admittedly, well-optimized) beating a $\Theta(n^{1/2})$ algorithm. The constants would have to be worse by a factor of $5\cdot10^6$ for that to happen, and there's nothing in the algorithm to suggest anything that bad.</p> <p>Of course I may have miscoded it (though I obtained the correct answer) or there may be reasons why the constant factors would be so high for this algorithm. But in any case this seemed suspicious enough to bring up here that I might be enlightened in any case.</p> <p>Of course even if the result claimed is not correct this is no mark against the author, as the paper is only a preprint and the claim is peripheral in any case.</p> <p>[1]: Jakub Pawlewicz, <a href="http://arxiv.org/abs/1107.4890" rel="nofollow">Counting square-free numbers</a> (2011), arXiv:1107.4890.</p> http://mathoverflow.net/questions/93916/sum-of-sum-k1ndk2 Sum of $\sum_{k=1}^nd(k^2)$ Charles 2012-04-12T22:58:52Z 2012-04-17T15:20:55Z <p>There is a literature dealing with $$\sum_{k\le x}d(f(k))$$ where $f$ is an irreducible polynomial and $d(n)$ is the number of divisors of $n$. Erdos 1952 shows that the sum $\asymp x\log x,$ which was improved to $Ax\log x+O(x\log\log x)$ by Bellman-Shapiro (cited in Scourﬁeld). But these results only apply to irreducible polynomials.</p> <ol> <li>What asymptotics are known for $\sum_{k\le x}d(k^2)$?</li> <li>Are there good methods for calculating this sum quickly?</li> </ol> <p>The literature includes: Dirichlet 1850, Voronoi 1903 and van der Corput 1922, Kolesnik 1969, Huxley 1993, Nowak 2001 (linear); Scourﬁeld 1961, Hooley 1963, McKee 1995, McKee 1997, McKee 1999, Broughan 2002 (quadratic). The sequence is in the OEIS as <a href="https://oeis.org/A061503" rel="nofollow">A061503</a> but there is no real information there.</p> http://mathoverflow.net/questions/92525/bounds-on-pseudosquares Bounds on pseudosquares Charles 2012-03-29T03:47:59Z 2012-04-03T23:29:34Z <p>Suppose $n\in\mathbb{Z}^+$ is a nonsquare in $\mathbb{Z}$ but is a square mod $2^2,3^2,4^2,5^2,\ldots,k^2.$ How small can $n$ be?</p> <p>On the ERH, there are no small pseudosquares: $L_p>e^{\sqrt{p/2}}$. Heuristically, more is true: $\log L_p\gg p/\log p.$ I am looking for an unconditional lower bound, even if very weak. Are any known?</p> <p>Even knowing that $L_p>p^3$ would be useful to me.</p> http://mathoverflow.net/questions/91915/detecting-recognizing-irrational-number-by-computers/91917#91917 Answer by Charles for Detecting/Recognizing Irrational Number by Computers Charles 2012-03-22T14:35:52Z 2012-03-22T14:35:52Z <p>Generate the continued fraction for the number. If it has a suspiciously* large number, truncate just before it: it's probably rational. Otherwise it's either irrational or rational with a large denominator; you can't easily tell the two apart.</p> <p>Of course since both rationals and irrationals are dense in the reals you can never know for sure with just an approximation, but this is a useful technique that often works in practice.</p> <p><em>*</em> This can be made more precise using the <a href="http://mathworld.wolfram.com/Gauss-KuzminDistribution.html" rel="nofollow">Gauss-Kuzmin distribution</a>. But you can probably just eyeball it.</p> http://mathoverflow.net/questions/91718/linear-combination-of-multiplicative-functions Linear combination of multiplicative functions Charles 2012-03-20T14:10:58Z 2012-03-20T14:10:58Z <p>Carlitz showed necessary and sufficient conditions for an arithmetic function to be a linear combination of two multiplicative functions. He mentions the possibility of generalizing to $k$ multiplicative functions, but as far as I can tell this was never published.</p> <p>What is known about arithmetic functions which can be represented as linear combinations of some fixed number $k$ of multiplicative functions? Given $k$, how many terms 1, 2, ..., n are needed to either reject it as a linear combination of $k$ multiplicative functions or to generate (partial) multiplicative functions and their coefficients?</p> <p>[1] L. Carlitz, <a href="http://www.collectanea.ub.edu/index.php/Collectanea/article/viewArticle/3347" rel="nofollow">Sums of arithmetic functions</a>, <em>Collectanea Mathematica</em> <strong>20</strong>:2 (1969), pp. 107-126.</p> http://mathoverflow.net/questions/84194/nonzero-digits-in-n Nonzero digits in n! Charles 2011-12-23T23:54:37Z 2011-12-24T00:11:41Z <p>Can it be shown that a positive fraction of the base-$b$ digits of n! are nonzero (in the limit as $n\to\infty$)?</p> http://mathoverflow.net/questions/39452/status-of-harvey-friedmans-grand-conjecture Status of Harvey Friedman's grand conjecture? Charles 2010-09-21T00:29:27Z 2011-12-02T07:43:08Z <p>Friedman [1] conjectured</p> <blockquote> <p>Every theorem published in the Annals of Mathematics whose statement involves only finitary mathematical objects (i.e., what logicians call an arithmetical statement) can be proved in <a href="http://www.math.ohio-state.edu/~friedman/pdf/GodelLect060202.pdf" rel="nofollow" title="exponential function arithmetic">EFA</a>. EFA is the weak fragment of Peano Arithmetic based on the usual quantifier free axioms for 0,1,+,x,exp, together with the scheme of induction for all formulas in the language all of whose quantifiers are bounded. This has not even been carefully established for Peano Arithmetic. It is widely believed to be true for Peano Arithmetic, and I think that in every case where a logician has taken the time to learn the proofs, that logician also sees how to prove the theorem in Peano Arithmetic. However, there are some proofs which are very difficult to understand for all but a few people that have appeared in the Annals of Mathematics - e.g., Wiles' proof of FLT.</p> </blockquote> <p>Have there been any serious challenges to this or the weaker conjecture with Peano arithmetic in place of exponential function arithmetic?</p> <p>[1] <a href="http://cs.nyu.edu/pipermail/fom/1999-April/003014.html" rel="nofollow">http://cs.nyu.edu/pipermail/fom/1999-April/003014.html</a></p> http://mathoverflow.net/questions/35927/asymptotic-density-of-k-almost-primes/36425#36425 Answer by Charles for Asymptotic density of k-almost primes Charles 2010-08-23T04:23:18Z 2011-12-01T07:11:38Z <p>I looked at $$\int_e^x\frac{(\log\log t)^{k-1}}{(k-1)!\log t}dt$$ to see if, empirically, the error was any less in the special case $k = 2,\ x = 2^n$ (semiprimes at powers of 2, as in <a href="http://oeis.org/classic/A125527" rel="nofollow">A125527</a>). Unfortunately the results were inconclusive. The error was smaller over the domain I checked: about half the error around a million, tapering down to a quarter less error at $2^{49}$. But everywhere I checked both estimates were too small, by significant relative factors.</p> <p>Further, these errors did not seem to taper off much. The error in $x\log\log x/\log x$ went from 10% to 8% fairly smoothly, while the error in the integral reached an apparent relative maximum around $2^{40}$, staying between 5% and 6% the whole way. This seems fundamentally unlike the behavior with Li and $x/\log x$ where the error in the latter (wrt $\pi(x)$) quickly outpaces the error in the former.</p> http://mathoverflow.net/questions/82062/determining-the-exceptional-set-in-the-theorem-of-ax-kochen Determining the exceptional set in the theorem of Ax & Kochen Charles 2011-11-28T08:59:18Z 2011-11-28T14:36:01Z <p>Ax &amp; Kochen [1] proved that for every $d\in\mathbb{N}$ there exists a finite set $A(d)$ such that for every prime $p\not\in A(d),$ every homogeneous polynomial of degree $d$ over $\mathbb{Q}_p$ in at least $d^2+1$ variables has a nontrivial zero.</p> <ol> <li><p>Is there an effective procedure for determining $A(d)$?</p></li> <li><p>For what values of $d$ is $A(d)$ known? Ax &amp; Kochen mention that the special cases $d\in{2,3,5,7,11}$ were known but not if $A$ was known for those cases.</p></li> </ol> <p>[1] James Ax and Simon Kochen, "Diophantine problems over local fields I.", <em>American Journal of Mathematics</em> <strong>87</strong> (1965), pp. 605&ndash;630.</p> <p>[2] Simon Kochen, "The model theory of local fields", <em>Lecture Notes in Mathematics</em> <strong>499</strong> (1975), pp. 384&ndash;425.</p> http://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/81533#81533 Answer by Charles for Fastest Algorithm to Compute the Sum of Primes? Charles 2011-11-21T17:26:37Z 2011-11-22T13:59:11Z <p>Deléglise-Dusart-Roblot [1] give an algorithm which determines $\pi(x,k,l)$, the number of primes up to $x$ that are congruent to $l$ modulo $k,$ in time $O(x^{2/3}/\log^2x).$ Using this algorithm to count the number of primes in all residue classes $k&lt;2\log x$ takes $$1+\sum_{p&lt;2\log x}(p-2)\sim\frac{2\log^2x}{\log\log x}$$ invocations of Deléglise-Dusart-Roblot for a total of $O(x^{2/3}/\log\log x)$ time.</p> <p>This allows one to determine the value of $\sum_{p\le x}p$ mod all primes up to $2\log x$ and hence, by the Prime Number Theorem and Chinese Remainder Theorem, the value of the sum mod $\exp(\vartheta(2\log x))=x^2(1+o(1)).$ Together with bounds on the value of $\sum_{p\le x}p$ [2], this allows the computation of the sum.</p> <p>Note that the primes slightly beyond $2\log x$ may be required depending on the value of $\vartheta(2\log x).$ Practically speaking, except for $x$ tiny, $2\log x+\log x/\log\log x$ suffices. This does not change the asymptotics.</p> <p>I do not know if it is possible to modify the Lagarias-Odlyzko analytic formula [3] to count in residue classes. If so, this would allow an $O(x^{1/2+o(1)})$ algorithm.</p> <h1>References</h1> <p>[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, <a href="http://www.ams.org/journals/mcom/2004-73-247/S0025-5718-04-01649-7/S0025-5718-04-01649-7.pdf" rel="nofollow">Counting primes in residue classes</a>, <em>Mathematics of Computation</em> <strong>73</strong>:247 (2004), pp. 1565-1575. <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.779" rel="nofollow">doi 10.1.1.100.779</a></p> <p>[2] Nilotpal Kanti Sinha, <a href="http://arxiv.org/abs/1011.1667" rel="nofollow">On the asymptotic expansion of the sum of the first n primes</a> (2010).</p> <p>[3] J. C. Lagarias and A. M. Odlyzko, <a href="http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf" rel="nofollow">Computing $\pi(x)$: An analytic method</a>, <em>Journal of Algorithms</em> <strong>8</strong> (1987), pp. 173-191.</p> http://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/81453#81453 Answer by Charles for Fastest Algorithm to Compute the Sum of Primes? Charles 2011-11-20T21:10:43Z 2011-11-20T21:10:43Z <p>This is a difficult problem. I asked about it <a href="http://math.stackexchange.com/q/28238/1778" rel="nofollow">here on math.se</a> and <a href="http://cstheory.stackexchange.com/q/5578/962" rel="nofollow">here on cstheory</a>. In both cases my question was somewhat broader: allowing sums over different exponents rather than just 1. In the second link I also allowed interactive proofs.</p> <p>I noted that for exponent 0 there are efficient algorithms (superior to enumerating primes): the various analytical or combinatorial $\pi(x)$ algorithms. But no one was able to suggest an efficient means to solve the problem for any exponent. An interactive proof was proposed that allows a person to check a proposed proof in linear time, but the confidence in the proof is asymptotically 0% against a cunning adversary.</p> <p>I am not aware of any hardness results, though, so this seems to be wide-open.</p> http://mathoverflow.net/questions/81427/the-universal-diophantine-equation/81428#81428 Answer by Charles for The "universal" diophantine equation Charles 2011-11-20T15:18:14Z 2011-11-20T15:18:14Z <p>Any Diophantine set can be enumerated, in the sense that there is a procedure that will list any given member of the set after a finite amount of time. In fact, Diophantine sets are precisely those which can be so listed: the recursively enumerable sets.</p> <p>For the primes and many other Diophantine sets, more is true: the elements can be listed in order, since there are procedures for determining not only existence but also non-existence. These sets are called <em>recursive</em> or <em>decidable</em>.</p> <p>You are right that finding a Diophantine representation for primes does not add much if anything to the study of primes. It serves, rather, to increase our understanding of Diophantine equations.</p> http://mathoverflow.net/questions/81085/interpreting-a-paper-primes-and-interval-size Interpreting a paper: primes and interval size Charles 2011-11-16T16:48:16Z 2011-11-16T17:49:20Z <p>I was reading the <a href="http://michaelnielsen.org/polymath1/index.php?title=Finding_primes" rel="nofollow">Polymath4</a> project and have trouble understanding one of the arguments. From page 6 of [1] (either the preprint or the final paper):</p> <blockquote> <p>For any j ≥ 2, the interval $[a^{1/j}, b^{1/j}]$ has size $O(N^c)$ (by the mean value theorem), and so the $j$th summand on the RHS can be computed in time $O(N^{c+o(1)})$ by the AKS algorithm.</p> </blockquote> <p>$c>0$ is an unspecified small constant and $N\le a\le b\le2N$ are arbitrary. $c$ is probably very tiny but implicitly $c&lt;0.22.$ The summand referenced is $\left|p\in[a^{1/j},b^{1/j}]: p\text{ prime}\right|.$</p> <p>I don't understand what's meant here. Taking, for concreteness, $j=2,a=N,b=2N$ this is:</p> <blockquote> <p>The interval $[\sqrt N, \sqrt{2N}]$ has size $O(N^c)=o(N^{0.22})$ (by the mean value theorem), and so $\left|p\in[\sqrt N, \sqrt{2N}]: p\text{ prime}\right|$ can be computed in time $O(N^{c+o(1)}).$</p> </blockquote> <p>If by size the authors meant the number of integers in the range it would be wrong: clearly that is $(\sqrt2-1)N^{0.5}+o(1)\neq o(N^{0.22}).$ But I can't think of another meaning that works here.</p> <p>Further, it's not even clear to me if the result can be salvaged. Counting the number of primes in the interval should take time $O(N^{0.25+o(1)})$ with the Lagarias-Odlyzko algorithm, so I can't even count the set in that time. (On the other hand, this does not jeopardize the theorem, for which the time need only be $O(N^{0.5-c+o(1)}).$)</p> <p>I must be misunderstanding something here; any help?</p> <h2>References</h2> <p>[1] Terence Tao, Ernest Croot III and Harald Helfgott, <a href="http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2011-02542-1/" rel="nofollow">Deterministic methods to find primes</a>, Mathematics of Computation (in press). <a href="http://arxiv.org/abs/1009.3956" rel="nofollow">arXiv:1009.3956</a></p> http://mathoverflow.net/questions/77231/strange-prime-number/77234#77234 Answer by Charles for "Strange" prime number" Charles 2011-10-05T13:40:35Z 2011-10-05T13:40:35Z <p>This is Sloane's <a href="https://oeis.org/A051362" rel="nofollow">A051362</a>. I expect it has only finitely many members, but I don't know of a proof.</p> <p><a href="http://math.stackexchange.com/q/33094/1778" rel="nofollow">One of the most popular math.se questions</a> addresses this precise question.</p> http://mathoverflow.net/questions/75637/is-there-a-two-variable-prime-representing-polynomial-in-the-sense-of-jones-sato Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)? Charles 2011-09-16T21:05:45Z 2011-10-04T15:21:46Z <p>In the math.se question <a href="http://math.stackexchange.com/q/59846/1778" rel="nofollow">Proof of no prime-representing polynomial in 2 variables</a>, Alon Amit asks if Ribenboim's claim that a prime-representing polynomial (a Diophantine polynomial in which the positive values are precisely the primes) must have at least three variables has been proven. Alon suggested that perhaps the number was a typo, that all that is known is that (trivially) no univariate polynomial is prime-representing.</p> <p>As of Jones 1982 [1, p. 550] the question of the existence of a universal Diophantine equation in two variables was open, so certainly it was not known that the number of variables for the special case of the primes was more than 2 at that time.</p> <p>[1] James P. Jones, "Universal Diophantine equation", <em>The Journal of Symbolic Logic</em> <strong>47</strong>:3 (1982), pp. 549-571.</p> http://mathoverflow.net/questions/75637/is-there-a-two-variable-prime-representing-polynomial-in-the-sense-of-jones-sato/77140#77140 Answer by Charles for Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)? Charles 2011-10-04T15:21:46Z 2011-10-04T15:21:46Z <p>Davis [1] writes that the two-variable case of universal Diophantine equations is still open as of 2006. (Ribenboim's book was published in 1996.) So the question of a prime-representing polynomial in two variables was (and, presumably, is) still open.</p> <p>[1] Martin Davis, <a href="http://cs.nyu.edu/pipermail/fom/2006-December/011184.html" rel="nofollow">[FOM] Decidability of Diophantine equations</a>, post to the FOM mailing list, December 14 2006.</p> http://mathoverflow.net/questions/127889/is-rigour-just-a-ritual-that-most-mathematicians-wish-to-get-rid-of-if-they-could Comment by Charles Charles 2013-04-18T14:55:13Z 2013-04-18T14:55:13Z This should be re-opened as CW. http://mathoverflow.net/questions/33045/product-over-the-primes Comment by Charles Charles 2013-04-16T14:25:25Z 2013-04-16T14:25:25Z @joro: I do not know of any reasonable lower bound. A crude one can be obtained with the prime zeta function. http://mathoverflow.net/questions/124500/sums-of-squares Comment by Charles Charles 2013-03-20T16:56:18Z 2013-03-20T16:56:18Z <a href="https://oeis.org/A069003" rel="nofollow">oeis.org/A069003</a> http://mathoverflow.net/questions/124707/does-erosion-mix-faster-than-a-riffle-shuffle/124721#124721 Comment by Charles Charles 2013-03-17T16:14:01Z 2013-03-17T16:14:01Z @Anthony Quas: But $K\approx2\sqrt n$ so the lower bound is just two shuffles. Right? http://mathoverflow.net/questions/59741/are-there-infinitely-many-triples-of-consecutive-square-free-integers/59746#59746 Comment by Charles Charles 2013-03-05T14:51:34Z 2013-03-05T14:51:34Z Dickson's conjecture does apply, you just have to use (say) 12n+1, 6n+1, and 4n+1. But that's a pretty big sledgehammer to apply to a little problem like this! http://mathoverflow.net/questions/119453/polynomial-time-algorithm-to-compare-numbers-in-conway-chained-arrow-notation/119465#119465 Comment by Charles Charles 2013-03-05T00:31:03Z 2013-03-05T00:31:03Z Robert Munafo writes that he knows Hypercalc cannot compute an ordering (or even a partial ordering) for chained-arrow notation, but he would love to learn of an algorithm that does. http://mathoverflow.net/questions/120886/aks-algorithm-pseudoprimes Comment by Charles Charles 2013-02-22T18:32:56Z 2013-02-22T18:32:56Z No solutions to (2) up to $10^9$. http://mathoverflow.net/questions/120886/aks-algorithm-pseudoprimes Comment by Charles Charles 2013-02-12T15:32:17Z 2013-02-12T15:32:17Z @Dominick Reinhold: Not much help for a = 1, though. http://mathoverflow.net/questions/113840/for-consecutive-primes-a-lt-b-lt-c-prove-that-ab-ge-c Comment by Charles Charles 2013-02-10T04:13:44Z 2013-02-10T04:13:44Z (Of course 2.001 can be replaced by 2 unconditionally.) http://mathoverflow.net/questions/104043/saying-things-rapidly-about-integer-factorisations/104045#104045 Comment by Charles Charles 2013-02-01T15:51:06Z 2013-02-01T15:51:06Z Finding the value of &quot;such-and-such&quot; seems very hard. http://mathoverflow.net/questions/120511/why-do-primes-dislike-dividing-the-sum-of-all-the-preceding-primes Comment by Charles Charles 2013-02-01T15:18:17Z 2013-02-01T15:18:17Z <a href="https://oeis.org/A007506" rel="nofollow">oeis.org/A007506</a> http://mathoverflow.net/questions/119980/concise-model-of-modern-fiat-money-and-its-non-conservation/120007#120007 Comment by Charles Charles 2013-01-27T17:08:40Z 2013-01-27T17:08:40Z Its assets are not quite separate from the US government, since it turns over its profits to the Treasury (in weekly payments based on last year's profit). http://mathoverflow.net/questions/38794/constructing-prime-numbers/38918#38918 Comment by Charles Charles 2013-01-21T17:00:24Z 2013-01-21T17:00:24Z @Denis: I think so. http://mathoverflow.net/questions/116806/any-published-references-for-this-on-time-on-epsilon-space-identity-for Comment by Charles Charles 2012-12-19T23:12:24Z 2012-12-19T23:12:24Z Perhaps you intended to write $O(n^\epsilon)$ space? This of course cannot be done in $O(\epsilon)=O(1)$ space. But I don't even see how that can be done. What is memoized and what is recomputed? http://mathoverflow.net/questions/116048/maximum-size-of-powers-with-a-given-difference/116073#116073 Comment by Charles Charles 2012-12-11T15:47:32Z 2012-12-11T15:47:32Z So the weaker version gives $a^x\ll n^{2+\varepsilon}$. But this applies only to the common case of exponents 2 and 3; is this the worst case?