MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following question:

1) For a given natural number $a$, are there finitely or infinitely many natural numbers that are not of the form $anm \pm n\pm m$, where $m$ and $n$ range over positive integers? (For $a=1$ or $a=2$ you have all the natural numbers.)

Does this problem appear in the literature?

As one can see at MO Scribe's question Chen's Theorem with congruence conditions. it is the same like asking if there are infinitely many $k$ such that both $ak+1$ and $ak-1$ do not have any non-trivial factors of the form $\pm 1 \mod a$.

I give a proof that for $a=6$ the question is equivalent to the twin prime conjecture so it is known that we don't have any proof. But what about other values of $a$? Is the problem for $a=100$ or more of the same difficulty?

2) Is the density (Szemeredi's or Schnirelman's), of the numbers that are not of the form, zero for any value of $a$?

3) From Viggo Brun's theorem we have that the sum of the reciprocals of the twin primes converges. Does the sum of the reciprocals for any value of $a$ of the numbers that are not of this form converge?

4)For a given natural number $a$ are there infinitely many $k$ such that both $ak+1$ , $ak-1$ do not have any $prime$ factors of the form $\pm 1 \mod a$? (the same questions for these $k$ as in 2) and 3) )

5) And the most easy : for which $a$ do we have a proof that there are infinetely many $k$ such that such that both $ak+1$ , $ak-1$ are either prime or can be written as a product of two numbers both not of the form $\pm 1 \mod a$? I guess that if $φ(a)$ is big enough we can have such a proof (the same questions for these $k$ as in 2) and 3) )

NOTE: In 1) and 4) both both $ak+1$ and $ak-1$ can be either primes or the product of primes not of the form $\pm 1 \mod a$ ,but in the 1) no subproduct of them can be of this form.

As MO Scribe noticed the conjectural answer is that there should be infinetely many such pairs because we are aspecting to have infinitely many prime pairs of any reasonable congruence condition.

There are infinitely many twin primes if and only if there are infinitely many natural numbers that are not of the form $6nm \pm n \pm m$.

Proof: Every number that is not a multiple of $2$ or $3$ is of the form $6N\pm 1$. So the only pairs that are not divisible by $2$ or $3$ are $(6N-1,6N+1)$ for any $N$. Now are there infinitely many such prime pairs (twin primes)?

If the number $6N-1$ is prime it should not be written as a product of some numbers $6n+1,6m-1$ for any $n,m > 0$. So $(6n+1)(6m-1)=6(6nm-n+m)-1$, which means that $N$ should not be of the form $6nm-n+m$ for any $n,m>0$.

Similarly, if $6N+1$ is a prime it should not be a product of some numbers $(6n-1)(6m-1) =6(6nm-n-m)+1$, or $(6n+1)(6m+1) =6(6nm+n+m)+1$. Which means that we have a prime couple of the form $(6N-1,6N+1)$ if and only if $N$ is not of the form $6nm \pm n \pm m$ for any $n,m$.

NOTE: After i have edited this observasion-question I realised that it is well known that for $a=6$ it is equivalent to twin prime conjecture (as it is written on the answer by Luis below too), a notice that S.Golomb seems to have done first, but my question is focused to the other values of $a$.

If someone want to add something

share|cite|improve this question
This does not look like a research-level question. I vote to close. If you provide more background and motivation of this question, I might reconsider. – André Henriques Dec 16 '10 at 14:36
do you have an easy answer for a say 100? – asterios gantzounis Dec 16 '10 at 14:41
I edited it. Is this what you meant to ask? – Todd Trimble Dec 16 '10 at 17:24
thank you m,n is not 0 – asterios gantzounis Dec 16 '10 at 17:25
I might point out what Gauss said regarding Fermat's equation $x^n+y^n=z^n$ - that it is one of a multitude of similar Diophantine equations he could come up with whose solution would be just as difficult. It may be that this is an open problem because no one has even thought to consider it. Even if someone has considered it, then it might not have received much attention, and thus not be a 'well-known' open problem. And even if it was fairly well-known, it might not have lead to any interesting mathematics or conjectures, and so isn't regarded as a 'famous' open problem. – David Roberts Jan 26 '11 at 23:06
up vote 22 down vote accepted

$\newcommand\Z{\mathbf{Z}}$ $\newcommand\Q{\mathbf{Q}}$

(Caveat: normally I wouldn't answer a question with such a limited knowledge of the general theory, but classical analytic number theory seems not so well represented by active MO members.)

Suppose that $A$ is a finite abelian group. Then I claim that given any set of at least $|A| + 1$ (not necessarily distinct) elements of $A$ one can find a proper subset whose sum is the identity. Proof: Denote the elements $a_i$ for $i = 1$ to $|A|+1$. By the pigeonhole principle, either one of the $|A|$ sums $\sum_{i=1}^{r} a_i$ for $r = 1$ to $|A|$ is the identity, or two of the sums are the same element of $|A|$, in which case consider the difference. We deduce from this the following: Let $n$ be any integer coprime to $a$ with more than $r:=|(\Z/a \Z)^{\times}|$ prime factors. Then $n$ has a proper divisor of the form $1 \mod a$.

Suppose that $k$ cannot be represented by the form $amn \pm m \pm n$, and suppose that $a > 2$. It is simple to deduce that this is equivalent to asking that $ak+1$ and $ak-1$ have no proper divisors of the form $\pm 1 \mod a$. It follows that $ak+1$ and $ak-1$ each have at most $r=|(\Z/a \Z)^{\times}|$ prime factors. The integers with at most $r$ prime factors are sometimes called $r$-almost primes. If $\pi_r(x)$ counts the number of $r$-almost primes $\le x$ then $$\pi_r(x) \sim \frac{x (\log \log x)^{r-1}}{\log(x)}.$$ (Compare this to the prime number theorem when $r = 1$.) In particular, we see that the $r$-almost primes have zero density (in any sense), and thus:

2) The density of integers that can not be represented in the form $amn + m + n$ is zero. Similarly, the density of integers that cannot be represented in the form $amn + m -n$ is zero. In particular, the density of the $a$-asterios numbers, the integers that can neither be represented in the form $amn+m+n$ nor $amn+m-n$, is zero.

Let $\pi_{r,2}(x)$ denote the number of twin $r$-almost primes less than or equal to $x$, that is, the number of integers $n \le x$ such that $n$ and $n+2$ are both $r$-almost primes. (For example, $\pi_{1,2}(x)$ counts the number of twin primes less than $x$.) What do we know about this function? Brun was the first to give an upper bound for $\pi_{r,2}(x)$ using sieving techniques. Refinements by others (in particular Selberg) allowed one to obtain the estimate $$\pi_{1,2}(x) \ll \frac{x}{(\log x)^2},$$ which gives the correct (conjectural) order of magnitude. Without going into the Selberg sieve, let me say that what these arguments really give is decent upper and lower bounds of the following kind (for large $x$): $$\frac{A x}{(\log x)^2} < \left\{n < x, \ p \nmid n(n+2) \ \text{if} \ p < x^{\alpha}\right\} < \frac{B x}{(\log x)^2}$$ for non-zero constants $A$ and $B$, where $0 < \alpha < 1$ is some fixed small constant, which we might imagine for the sake of argument is $1/10$. Since every twin prime $>x^{\alpha}$ contributes to this sum, this gives the correct (up to a constant) upper bound for $\pi_{1,2}(x)$. It also gives a lower bound for $\pi_{10,2}(x)$, since if every factor of $n < x$ is at least $x^{1/10}$, then $n$ has at most $10$ prime factors.

The motto I learnt about sieving was the following: upper bounds are easy, lower bounds are hard. Thus, since we are interested in bounding $\pi_{r,2}(x)$, it seems that we are in good shape. However, there is a subtlety here. Let $\pi(x,z)$ denote the number of integers $n$ less than $x$ such that every prime factor of $n$ is at least $z$. It's clear by the argument of the last paragraph that $\pi_r(x) \ge \pi(x,x^{1/r})$. One might imagine that these numbers are roughly of the same magnitute. However, it turns out that $\pi_r(x)$ is much bigger than $\pi(x,x^{1/r})$. The latter is comparable to the number of primes less than $x$, where the former has an extra factor of $(\log \log x)^{r-1}$. The reason is that $\pi_r(x)$ is dominated by numbers with (a few) small prime factors. In fact, as Kowalski pointed out to me, it is not even obvious that one can easily obtain the correct upper bound for $\pi_r(x)$ simply by sieving over primes. From the asymptotic for $\pi_{r}(x)$, one expects that $$(*): \qquad \pi_{r,2}(x) =^{?} \ O\left(\frac{x (\log \log x)^{2r-2}}{(\log x)^2}\right).$$ (EDIT: My resident expert reports that this is known. Here is a sketch of the idea in the simpler case where we want to count pairs $n$ and $n+2$ where $n$ is a $2$-almost prime and $n+2$ is prime. First, for a small prime $p$, we want to find an upper bound for the number of $n < x$ such that $n$ is divisible by $p$ and both $n/p$ and $n+2$ are prime. This is a similar problem to counting twin primes, and in a similar way one obtains a bound of the form $O(x/\log x)$ (key point: the implied constant does not depend on $p$). If we wish to bound the number of pairs $(n,n+2)$ such that $n+2$ is prime and $n$ is a $2$-almost prime, we may instead count the triples $(p,n,n+2)$ where $p < x$ is prime, $n < x$ is divisible by $p$, $n/p$ is prime, and $n+2$ is prime. If for each $p < x$ we have a upper bound of $Ax/\log x$ (for the same $A$), in total we obtain the upper bound: $$ \frac{Ax}{\log x} \cdot \sum_{p < x} \frac{1}{p} \sim \frac{Ax \log \log x}{\log x}.$$ Of course, the devil is in the details! END EDIT) All one needs to answer 3) is that the exponent of $\log(x)$ in the denominator is $> 1$.

3). Assuming the expected result (*), the inverse sum of the $a$-asterios primes converges.

Consider the set of integers $S_a$ which do not have any prime factors of the form $\pm 1 \mod a$. This is a reasonable thing to do whenever $|(\Z/a\Z)^{\times}| > 2$. This is a weaker condition, so there are more of these numbers and consequently obtaining upper bounds is harder. We may form the Dirichlet series $$L(s) = \sum_{S_a} \frac{1}{n^s}$$ which has an Euler product: $$L(s) = \prod_{p \not\equiv \pm 1} \left(1 - \frac{1}{p^s}\right)^{-1}$$ Now let $K = \Q(\zeta_a)^{+}$ be the totally real subfield of $\Q(\zeta_a)$. It has degree $r/2 = \phi(a)/2$, where $r > 2$ unless $a = 1,2,3,4$ or $6$. (What we say now only makes sense for $r \ge 2$, in which case $r/2 \in \Z$.) A prime splits completely in $K$ if and only if it is of the form $\pm 1 \mod a$. Looking at the Euler product of $\zeta_K(s)$, we see that, up to a constant which can be explicitly written as some product over primes, $$\zeta_K(s) L(s)^{r/2} \sim \zeta_{\Q}(s)^{r/2}$$ as $s \rightarrow 1^{+}$, and hence $L(s) \sim (s-1)^{(2-r)/r}$ (up to some constant) as $s \rightarrow 1^{+}$. We deduce (Perron's formula) that the number of integers $\le x$ all of whose prime factors are not of the form $\pm 1 \mod a$ is asymptotic to $$ \kappa \cdot \frac{x}{(\log x)^{2/r}},$$ for some non-zero constant $\kappa$. This is the same analysis that gives the asymptotic formula for the number of integers $\le x$ which can be written as a sum of two squares (a result of Landau). We immediately deduce:

4a) The number of integers $a$ such that $ak+1$ (or $ak-1$) has no prime factors of the form $\pm 1 \mod a$ has zero density.

If $r > 2$ (so $a \ge 3$ and $a \ne 3,4,6$) then the power $2/r$ of $(\log x)$ is at most $1/2$. Thus, we actually are led to the following guess:

4b) If $r = \phi(a) > 2$, then one would heuristically expect the inverse sum of integers $k$ such that none of the prime factors of $ak-1$ and $ak+1$ are $\pm 1 \mod a$ diverges. If $r = 2$, so $a = 3$, $4$, or $6$, then (Brun) the series converges.

Here is a related problem of the very same kind: can one count the number of integers $n \le x$ such that both $n$ and $n+1$ can be expressed as the sum of two squares, and prove that there are $\sim x/\log(x)$ such integers (perhaps up to non-zero constant factors)?

Any integer $n$ can be written as the product of two numbers not of the form $\pm 1$ unless every prime factor of $n$ is of the form $\pm 1 \mod a$. The integers all of whose prime factors are $\pm 1 \mod a$ can be analyzed exactly as in the last paragraph. In this case, the number of integers all of whose prime factors are of the form $\pm 1 \mod a$ is asymptotic to $$ \kappa \cdot \frac{x}{(\log x)^{(1-2/r)}}.$$ Suppose that $r > 2$. Then the set of such integers has density zero, and thus the set of integers which have a factor not of the form $\pm 1 \mod a$ has density one. Any set of density one has infinitely many "twins" satisfying any fixed congruence condition. Hence:

5) If $r = \phi(a) > 2$, then there are infinitely many $k$ such that both $ak+1$ and $ak-1$ have a factor not of the form $\pm 1 \mod a$. Indeed, such numbers have density one.

Finally, I have nothing to say about problem 1) besides the remarks I made in my rephrasing of the original question here:

Chen's Theorem with congruence conditions.

share|cite|improve this answer
Wow! Nice answer, MO Scribe, for what seemed like a questionable question when it was first posed. +1 (and +1 again, in imaginary votes) – David Roberts Feb 3 '11 at 6:22
MO Scribe thank you very much for your interest and for your explicit answer! and of course for your first question too! So it seems that my first question is as difficult as the TPC?Of course i would like too keep contuct with you,if wanted send an email too me ...Thanks a lot ,please add on your answer any new information ,regards Asterios – asterios gantzounis Feb 3 '11 at 13:28
ubderstood the point of your answer ,thank you a lot. – asterios gantzounis Feb 4 '11 at 7:09
i have some ideas of how to go further but i need some experts advice, if you are interested send me an e mail – asterios gantzounis Feb 8 '11 at 12:01

Quoted from: A Selection of problems in the Theory of Numbers, by Waclaw Sierpinski, (1964)

page 104, line 13, problem $P_{19}^2$

Do there exist infinitely many twin primes ?

page 120, line 19, problem $P_{96}^2$

Do there exist infinitely many natural numbers which cannot be put in any of the four forms $6xy \pm x \pm y$ where $x$ and $y$ are natural numbers ?

lines 20 and 21, page 120:

It can be shown that question $P_{96}^2$ is equivalent to question $P_{19}^2.$

share|cite|improve this answer
Thank you , I am alredy aware of this . I had made the equivalence observation many years ago butS.Golomb made it before me.The question is focused on the other values of a – asterios gantzounis Jan 27 '11 at 7:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.