5
$\begingroup$

I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:

Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary predicate $P$, then if:

For all integers $M$, when randomly choosing a set of integers $R$ by including $n$ if $(n, M) = 1$ and with probability $\frac M{\max(M, \varphi(M)\log n)}$, the probability that $s$ is correct when $P(n) := n \in R$ is $1$.

Then $s$ is correct for $P(n) := n\text{ is prime}$.

Obviously, I don't expect a proof of this conjecture, as it immediately gives Dickson's conjecture, the asymptotic Goldbach conjecture, and some other open problems.

Has this conjecture been formulated before? Alternatively, is there a known counterexample? What if the probability is only required to be greater than $0$, not $1$?

Edit: There's also an iff version, by adding a number $m_0 = m_0(s)$, requiring that $m_0 \mid M$, adding to $R$ all prime divisors of $M$, and allowing any probability greater than $0$. I'm also interested in a counterexample for this, in either direction.

Improve this question
$\endgroup$
5
  • $\begingroup$ Incomprehensible. $\endgroup$
    – Gerry Myerson
    Commented Apr 4 at 4:22
  • 3
    $\begingroup$ @GerryMyerson Could you be a bit more specific? I'd be happy to clarify anything $\endgroup$
    – Daniel Weber
    Commented Apr 4 at 4:32
  • $\begingroup$ Maybe an example? $\endgroup$
    – Gerry Myerson
    Commented Apr 4 at 6:06
  • 5
    $\begingroup$ For what? How the conjecture can be used? For example, consider $s = \forall n, \exists m,n<m\land Pm\land P(m+2)$. If $P$ is assigned the meaning of "$n$ is prime", this is the twin primes conjecture. My conjecture could show it - for any number $M$, we can notice (by CRT) that there must be a number $a$ such that both $a$ and $a+2$ are coprime to $M$. Now the expected number of twins with this modular value is $\sum_n \frac{M}{\varphi (M) \log(M n + a)} \frac{M}{\varphi (M) \log(M n + a + 2)} = \infty$, so with probability 1 there are infinitely many twins for a random $R$. $\endgroup$
    – Daniel Weber
    Commented Apr 4 at 6:27
  • $\begingroup$ I have a meta-question, which is whether the second paragraph in the conjecture's statement is algorithmically decidable (i.e., whether given $s$ we can algorithmically decide whether for all $M$ the probability (…) is $1$). Maybe this should be made into a separate question. $\endgroup$
    – Gro-Tsen
    Commented Sep 24 at 21:33

1 Answer 1

Reset to default
3
$\begingroup$

Let me sketch why this question is hard. The function $f$ that takes a natural number $a$ to $$\min \{ b \mid \forall c\leq a, \exists d \in [c,c+b] : P(d)\}$$ has for the random set $R$ a size of approximately $(\log a)^2$: The number of elements satisfying $P$ in an interval of length $b$ is distributed approximately like a Poisson random variable with mean $b/\log a$, so has about an $e^{- b/\log a}$ probability of vanishing, so we expect it vanishes for none of the $a$ possible intervals if $b$ is larger than $(\log a)^2$.

This function is clearly definable in your language.

The inverse function will have an exponential growth rate. You can make a function that grows literally exponentially by $f^{-1} (f^{-1} (f(f(n))/4))$ and using this you can make a two-variable function that grows very roughly like the product of the two variables.

The fact that these functions are highly random makes it hard for me to see if one can use them to encode computation but including such functions certainly makes the nice properties of Presburger arithmetic that let us bound the complexity of any definable set disappear (vague since I am not very familiar with model theory). So it doesn't seem like one can "classify" all statements in this language in a way that lets us compare to known number-theoretic conjectures like the Hardy-Littlewood conjecture (which does suffice to resolve a lot of statements in this language).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .