1
$\begingroup$

Consider a system of $n$ divisibility conditions on $n$ prime variables: $$p_i|a_{i,1} p_1 + \dotsc + a_{i,n} p_n,\;\;\;\;\;1\leq i\leq n,$$ where $a_{i,j}$ are bounded integers. How many solutions are there with all $p_i$ prime, distinct and in a range $[N_0,N_1]$? (We can assume that $N_0$ is quite a bit larger than all $a_{i,j}$.) Or, put otherwise: under what conditions are there very few solutions?


Of course, some conditions are needed on $a_{i,j}$ for the system to have few solutions: if $a_{i,j}=0$ for all $(i,j)$, the system does have very many solutions!

Further thoughts: to make the question more precise, we may require each $p_i$ to be in a dyadic interval $\lbrack M_i, 2 M_i\rbrack$, and write $N_0$ for $\max_i M_i$. Can we hope (given $a_{i,j}$ not terribly degenerate) for a bound of the form $$\leq \frac{\prod_i O(M_i)}{N_0^n} \;\;\;\;\text{or, even better,} \leq \frac{\prod_i O(M_i/\log M_i)}{N_0^n}$$ on the total number of solutions? (See the comments below for an example suggesting that such a bound would be tight.)

If all $M_i$ are equal (or bounded by $O(N_0)$, say) then the divisibility conditions can be replaced by a system of equations $c_i p_i = a_{i,1} p_1 + \dotsc + a_{i,n} p_n$, $c_i$ bounded. That is a system of $n$ equations in $n$ variables, and thus should not in general have non-trivial solutions (meaning: it will not have solutions, as $0$ is not a prime). (Note in passing the case $c_i = \sum_{j} a_{i, j}$, which gives a solution with $p_i$ non-distinct, and in fact all the same; we are not counting such solutions, but it's good to keep them in mind.) So it is really the case of $M_i$ not all of the same size that is interesting.

Already a bound of the form $$\leq \frac{\prod_i O(M_i)}{N_0^{n/2}},$$ say, would be non-obvious and useful. An elementary solution could be particularly nice.

$\endgroup$
7
  • $\begingroup$ There is the obvious solution of all p_j being the same prime; the count reduces to an expression using $\pi()$ which I leave to you. For a solution with two different primes the question becomes interesting: it is like partitioning the columns coefficients into consistent groups which add to zero mod p or mod q, and this has a computer science/combinatorics feel. Of course, if N is larger than (some function of) the sum of coefficients (assuming all the a's are positive), there is no solution. Gerhard "Maybe Can't Have Largest Prime?" Paseman, 2019.03.24. $\endgroup$ Mar 24, 2019 at 18:46
  • $\begingroup$ For a non-dyadic interval (or for $p_i$ in different dyadic intervals), why would there be no solution? Yes, assume $N_0$ is larger than a large constant? $\endgroup$
    – Nell
    Mar 24, 2019 at 19:14
  • $\begingroup$ Here's an example showing a non-obvious situation where there could be more than very few solutions (though still not many). Consider the system $$\begin{matrix} p_1 &| p_3 + p_4 +p_5\\ p_2 &| p_3 + p_4 +p_5 \\ p_3 &| p_4 +p_5 -p_1-p_2\\ p_5 &| -p_2-p_1-p_3\\ p_4 &| -p_2-p_1-p_3.\end{matrix}$$ Let $p_1,p_2,p_4,p_5$ be in a range $[N,2N]$, but let $p_3$ be in a dyadic range $[N',2 N']$ with $N$ considerably larger than $N$. $\endgroup$
    – Nell
    Mar 24, 2019 at 21:34
  • $\begingroup$ (continued) Let us consider the solutions with $p_4+p_5-p_1-p_2=0$. Then the third divisibility condition is trivial, and the other conditions can be rewritten as follows: $p_3\equiv p_1 + p_2 \mod p_1 p_2$, $p_3\equiv -p_4 -p_5 \mod p_4 p_5$. There is one such $p_3$ in every interval of length $p_1 p_2 p_3 p_4$. If $N'\gg N^4$, the total number of solutions is $\ll N^4 N'/(N\cdot N^4) = N'/N$, which is not so many (and not so few). We should expect about the same number for $N\ll N'\ll N^4$, but that seems trickier to prove, doesn't it? $\endgroup$
    – Nell
    Mar 24, 2019 at 21:43
  • $\begingroup$ In your system, p3 has to be of size p1p2 and p4p5, so indeed much larger than N, and the middle sum has to sum to zero. For low rank systems of equations, a sum has to be both about a small constant (related to max of a's) times n times the average (size of the) prime, and has to be 0 mod the product of some of those primes. Then either the primes have to be smaller than this small constant times n, or else the sum has to be 0 mod all primes, or 0. This does not bode well if n and all the coefficients are odd, for example. Gerhard "There Are Other Nonsolvable Cases" Paseman, 2019.03.24. $\endgroup$ Mar 24, 2019 at 22:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.