Proving all sufficiently large integers can be written in the form $a^2+pq$.

Question

This is one of those numerous questions I ask myself, and to which I seem unable to answer:

Can every integer greater then $657$ be written in the form $a^2+pq$, with $a\in\mathbb Z$ and $p,q$ prime?

A quick brute force check trough numbers up to $100000$ told me that the only positive integers that can not be represented in the given form are $1, 2, 3, 12, 17, 28, 32, 72, 108, 117, 297$ and $657$.

The above conjecture seems quite likely to me. Since pretty much integers are of the form $pq$, it is quite probable that, given a large $n>0$, at least one of $n, n-1, n-2^2, n-3^2, \ldots$ is of the form $pq$.

I.e, considering the set $F=\{4,6,9,10,14,15,21,22,25,26,\ldots\}$ of all numbers of the form $pq$, a number $n$ not satisfying the property implies that none of the integers $n, n-1^2,\ldots, n-\lfloor\sqrt n\rfloor^2$ is an element of $F$.

It's not much, but that's all I've discovered so far.

(Besides, is there any hope solving this riddle without using complicated analytic number theory?)

Answer 1

This is very hard.

(Notation: A semiprime is a product of exactly two distinct primes.)

Just consider this problem for perfect squares. We're looking at the equation $b^2=a^2+pq$, which easily translates to $$(b-a)(b+a)=pq.$$ For fixed $b$, this is soluble in $a$ (and $p$ and $q$), precisely if either: 1) $2b-1$ is a semiprime, and we take $a=b-1$, or 2) There are primes $p$ and $q$ such that $p+q=2b$. If we assume that $2b-1$ is not a semiprime (and this is true for most $b$ -- looking at $b<x$, there are $O(x \frac{\log\log x}{\log x})$ values of $b$ for which $2b-1$ is a semiprime), we're therefore reduced to solving the Goldbach problem, and I don't know how to say anything useful about that (though I wish I did!). Thus, proving that every large integer $n$ can be written as $a^2+pq$ is at least as hard as proving Goldbach (or, I guess, proving Goldbach for a large subset of the even integers, those that aren't one more than a semiprime, but that's probably just as hard).

Answer 2

I believe that proving that every large $n$ can be represented as $a^2+pq$ is difficult, and I am not sure if it can be solved using known techniques. There is a basic way to prove that $A$ comprises a positive proportion of integers, and I have included this at the end, but it is a weak result. However, we can prove result you want if we are allowed to change signs.

Theorem: Every non-square integer $n$ may be written as $$n=a^2-pq$$ where $p,q$ are primes.

This follows from the main result of this paper of Robert Lemke Oliver Given $n\neq k^2$, the polynomial $x^2-n$ will represent infinitely many semi primes, and so we have infinitely many solutions to $x^2-pq=n$.

A positive proportion:

Theorem: Let $A=\{n: n=a^2+pq\}$. Then there exists $c>0$ such that $$\sum_{n\leq x} 1_A(n)>cx.$$

Proof sketch: By the Cauchy-Schwarz, inequality, we have that $$\left(\sum_{n\leq x} \sum_{n=a^2+pq} 1\right)^2 \leq \left(\sum_{n\leq x} 1_A(n)\right)\left(\sum_{n\leq x} \left(\sum_{n=a^2+pq} 1\right)^2\right).$$ Switching the orders of summation and using some basic estimates about primes we can prove that $$\sum_{n\leq x} \sum_{n=a^2+pq} 1\sim \frac{x^{3/2}\log \log x}{\log x},$$ and $$\sum_{n\leq x} \left(\sum_{n=a^2+pq} 1\right)^2 \ll \frac{x^{2}(\log \log x)^2}{(\log x)^2}.$$ Together with our Cauchy-Schwarz inequality, these bounds imply that $$|A\cap\{1,2,\dots,[x]\}|\gg x,$$ as desired.