User charles - MathOverflow

Product over the primes

2010-07-23T05:12:47Z

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.

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.

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.

Any suggestions for the calculation, or different approaches to the problem, would be appreciated.

[1] http://oeis.org/classic/A070284

Answer by Charles for At what point would an elementary generalization of Bertrand's Postulate be interesting?

2013-04-11T14:31:21Z

I think that it would be interesting if it has an effective (and not too huge) value of $X$.

Asymptotic density of k-almost primes

2010-08-18T04:37:54Z

Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-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$.

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

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

Partial results

Montgomery & 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$.

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.

References

[1] M. Cipolla, “La determinazione assintotica dell n$^\mathrm{imo}$ numero primo”, Matematiche Napoli 3 (1902), pp. 132-166.

[2] Pierre Dusart, "Estimates of Some Functions Over Primes without R.H." (2010) http://arxiv.org/abs/1002.0442

[3] Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres premiers" (1998) http://www.unilim.fr/laco/theses/1998/T1998_01.html

[4] Helge von Koch, "Sur la distribution des nombres premiers". Acta Mathematica 24:1 (1901), pp. 159-182.

[5] Hugh Montgomery & Robert Vaughan, Multiplicative Number Theory I. Classical Theory. (2007). Cambridge University Press.

[6] Lowell Schoenfeld, "Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x). II". Mathematics of Computation 30:134 (1976), pp. 337-360.

[7] Robert G. Wilson v, Number of semiprimes <= 2^n. In Sloane's On-Line Encyclopedia of Integer Sequences, A125527. http://oeis.org/classic/A125527 ; c.f. http://oeis.org/classic/A007053

Maximum size of powers with a given difference

2012-12-11T06:01:38Z

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.

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$?

$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?

Proving a least prime factor

2012-11-26T07:52:13Z

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

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?

Of course this is (fairly) easy to determine with high probability: run an appropriate number of ECM curves. But can this be done deterministically?

Analytic lower bounds on the first sign change of pi(x) - li(x)?

2010-12-06T17:37:03Z

There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & Demichel. These provide upper bounds (as well as lower bounds on some region in which $\pi(x)>{\mathrm{li}}(x)$).

Could these methods be used to generate a lower bound? That is, a region [2, y] in which $\pi(x)<{\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.)

It seems unlikely that direct searches like [2] will ever be able to resolve the exact value of the first crossing.

[1] C. Bays and R. H. Hudson. "A new bound for the smallest x with $\pi(x)>{\mathrm{li}}(x)$" Mathematics of Computation 69 (2000), pp. 1285–1296.

[2] T. Kotnik. "The prime-counting function and its analytic approximations", Advances in Computational Mathematics 29 (2008), pp. 55-70.

[2] R. Sherman Lehman. "On the difference $\pi(x)-{\mathrm{li}}(x)$" Acta Arithmetica 11 (1965), pp. 397–410.

[3] H. J. J. te Riele. "On the sign of the difference $\pi(x)-{\mathrm{li}}(x)$" Mathematics of Computation 48 (1987), pp. 323–328.

[4] Yannick Saouter and Patrick Demichel. "A sharp region where $\pi(x)-{\mathrm{li}}(x)$ is positive" Mathematics of Computation 79 (2010), pp. 2395-2405.

Answer by Charles for Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem?

2010-10-16T18:46:35Z

Using Robbins' [1] form of Stirling's formula,

$$\sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n+1))< n!< \sqrt{2\pi}n^{n+1/2}\exp(-n+1/(12n))$$

we get

$$\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$$

which is accurate enough to distinguish prime from composite for $n\le8$. For larger numbers, the error bound is too large.

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.

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.

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.

[1] H. Robbins, "A Remark on Stirling's Formula." The American Mathematical Monthly 62 (1955), pp. 26-29.

Large gaps between P2s

2012-09-08T19:14:11Z

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

I am interested in both unconditional results and those conditional on standard hypotheses.

Related result: Harman (1981) showed that almost all intervals of length $(\log x)^{7+\varepsilon}$ contains a $P_2.$

Upper bounds on the difference of consecutive zeta zeros

2012-01-05T18:54:00Z

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.

Any ideas?

I asked the question on math.se but did not get an answer.

Prescribed values for the uniform density

2012-07-25T17:10:46Z

Strauch & 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].

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.$

Is there a similar result with the uniform densities? $$ \underline{u}(A)=\lim_s\frac1s\liminf_n\sum_\stackrel{a\in A}{\ n < a\le n+s}1 $$ $$ \overline{u}(A)=\lim_s\frac1s\limsup_n\sum_\stackrel{a\in A}{\ n < a\le n+s}1 $$

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.

[1] Strauch and Tóth, Asymptotic density of $A\subset N$ and density of the ratio set $R(A)$. Acta Arith. 87 (1998), pp. 67-78.

[2] Ladislav Mišík, Sets of positive integers with prescribed values of densities, Mathematica Slovaca 52:3 (2002), pp. 289-296.

Lacunary sequence

2012-07-24T15:38:18Z

Is there a standard definition for a lacunary sequence?

Suppose $0 < a_1 < a_2 < \cdots.$

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. $$

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.

Further, the EOM entry for lacunary sequence is different from both (a finite form of the first): $$ \frac{a_{n+1}}{a_n}\ge\lambda>1. $$

Product of Fibonacci numbers

2012-07-18T13:36:30Z

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

What is known, asymptotically, about the growth of $f$?

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$.

Sum of the sum-of-divisors function

2012-06-19T18:00:33Z

I was looking at the abstract 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). $$

But I cannot find the above—or indeed, anything approaching it—in [2]. Have I missed something?

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.$

References

[1] Y.-F. S. Pétermann, "An Ω-theorem for an error term related to the sum-of-divisors function", Monatshefte für Mathematik 103:2 (1987), pp. 145-157.

[2] T. H. Gronwall, "Some asymptotic expressions in the theory of numbers", Trans. Amer. Math. Soc. 14 (1913), pp. 113–122. JSTOR

[3] S. Wigert, Sur quelques fonctions arithmétiques, Acta Math. 37 (1914), pp. 113–140.

Answer by Charles for Not especially famous, long-open problems which anyone can understand

2012-06-21T19:15:02Z

A meta-answer: I recommend Guy's Unsolved Problems in Number Theory and perhaps some of his others (Unsolved Problems in Geometry, Unsolved Problems in Combinatorial Games), which have many unsolved problems (both well-known and obscure), grouped into categories. Many of these are of attackable difficulty.

Mertens' function in time $O(\sqrt x)$

2012-05-02T05:38:57Z

This MathOverflow question 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).

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.

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.

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.

Third, on coding the algorithm I found it to be very slow. In fact, it was slower for those values tested than sum(n=1, 10^7, moebius(n)) in GP 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.

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.

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.

[1]: Jakub Pawlewicz, Counting square-free numbers (2011), arXiv:1107.4890.

Sum of $\sum_{k=1}^nd(k^2)$

2012-04-12T22:58:52Z

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.

What asymptotics are known for $\sum_{k\le x}d(k^2)$?
Are there good methods for calculating this sum quickly?

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 A061503 but there is no real information there.

Bounds on pseudosquares

2012-03-29T03:47:59Z

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?

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?

Even knowing that $L_p>p^3$ would be useful to me.

Answer by Charles for Detecting/Recognizing Irrational Number by Computers

2012-03-22T14:35:52Z

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.

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.

* This can be made more precise using the Gauss-Kuzmin distribution. But you can probably just eyeball it.

Linear combination of multiplicative functions

2012-03-20T14:10:58Z

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.

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?

[1] L. Carlitz, Sums of arithmetic functions, Collectanea Mathematica 20:2 (1969), pp. 107-126.

Nonzero digits in n!

2011-12-23T23:54:37Z

Can it be shown that a positive fraction of the base-$b$ digits of n! are nonzero (in the limit as $n\to\infty$)?

Status of Harvey Friedman's grand conjecture?

2010-09-21T00:29:27Z

Friedman [1] conjectured

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 EFA. 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.

Have there been any serious challenges to this or the weaker conjecture with Peano arithmetic in place of exponential function arithmetic?

[1] http://cs.nyu.edu/pipermail/fom/1999-April/003014.html

Answer by Charles for Asymptotic density of k-almost primes

2010-08-23T04:23:18Z

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

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.

Determining the exceptional set in the theorem of Ax & Kochen

2011-11-28T08:59:18Z

Ax & 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.

Is there an effective procedure for determining $A(d)$?
For what values of $d$ is $A(d)$ known? Ax & Kochen mention that the special cases $d\in{2,3,5,7,11}$ were known but not if $A$ was known for those cases.

[1] James Ax and Simon Kochen, "Diophantine problems over local fields I.", American Journal of Mathematics 87 (1965), pp. 605–630.

[2] Simon Kochen, "The model theory of local fields", Lecture Notes in Mathematics 499 (1975), pp. 384–425.

Answer by Charles for Fastest Algorithm to Compute the Sum of Primes?

2011-11-21T17:26:37Z

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<2\log x$ takes $$1+\sum_{p<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.

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.

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.

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.

References

[1] Marc Deléglise, Pierre Dusart, and Xavier-François Roblot, Counting primes in residue classes, Mathematics of Computation 73:247 (2004), pp. 1565-1575. doi 10.1.1.100.779

[2] Nilotpal Kanti Sinha, On the asymptotic expansion of the sum of the first n primes (2010).

[3] J. C. Lagarias and A. M. Odlyzko, Computing $\pi(x)$: An analytic method, Journal of Algorithms 8 (1987), pp. 173-191.

Answer by Charles for Fastest Algorithm to Compute the Sum of Primes?

2011-11-20T21:10:43Z

This is a difficult problem. I asked about it here on math.se and here on cstheory. 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.

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.

I am not aware of any hardness results, though, so this seems to be wide-open.

Answer by Charles for The "universal" diophantine equation

2011-11-20T15:18:14Z

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.

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 recursive or decidable.

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.

Interpreting a paper: primes and interval size

2011-11-16T16:48:16Z

I was reading the Polymath4 project and have trouble understanding one of the arguments. From page 6 of [1] (either the preprint or the final paper):

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.

$c>0$ is an unspecified small constant and $N\le a\le b\le2N$ are arbitrary. $c$ is probably very tiny but implicitly $c<0.22.$ The summand referenced is $\left|p\in[a^{1/j},b^{1/j}]: p\text{ prime}\right|.$

I don't understand what's meant here. Taking, for concreteness, $j=2,a=N,b=2N$ this is:

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

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.

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

I must be misunderstanding something here; any help?

References

[1] Terence Tao, Ernest Croot III and Harald Helfgott, Deterministic methods to find primes, Mathematics of Computation (in press). arXiv:1009.3956

Answer by Charles for "Strange" prime number"

2011-10-05T13:40:35Z

This is Sloane's A051362. I expect it has only finitely many members, but I don't know of a proof.

One of the most popular math.se questions addresses this precise question.

Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?

2011-09-16T21:05:45Z

In the math.se question Proof of no prime-representing polynomial in 2 variables, 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.

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.

[1] James P. Jones, "Universal Diophantine equation", The Journal of Symbolic Logic 47:3 (1982), pp. 549-571.

Answer by Charles for Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?

2011-10-04T15:21:46Z

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.

[1] Martin Davis, [FOM] Decidability of Diophantine equations, post to the FOM mailing list, December 14 2006.

Comment by Charles

2013-04-18T14:55:13Z

This should be re-opened as CW.

Comment by Charles

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.

Comment by Charles

2013-03-20T16:56:18Z

oeis.org/A069003

Comment by Charles

2013-03-17T16:14:01Z

@Anthony Quas: But $K\approx2\sqrt n$ so the lower bound is just two shuffles. Right?

Comment by Charles

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!

Comment by Charles

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.

Comment by Charles

2013-02-22T18:32:56Z

No solutions to (2) up to $10^9$.

Comment by Charles

2013-02-12T15:32:17Z

@Dominick Reinhold: Not much help for a = 1, though.

Comment by Charles

2013-02-10T04:13:44Z

(Of course 2.001 can be replaced by 2 unconditionally.)

Comment by Charles

2013-02-01T15:51:06Z

Finding the value of "such-and-such" seems very hard.

Comment by Charles

2013-02-01T15:18:17Z

oeis.org/A007506

Comment by Charles

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

Comment by Charles

2013-01-21T17:00:24Z

@Denis: I think so.

Comment by Charles

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?

Comment by Charles

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?