5

Does the antidiagonal in the square matrix with entries $1,2,\ldots,n^2$ row by row in that order always contain a prime?

For example:

For n=2: $\begin{bmatrix}1 & 2\\3 & 4\end{bmatrix}$ the antidiagonal contains two primes (2,3).

For n=3: $\begin{bmatrix}1 & 2&3\\4&5&6\\ 7&8& 9\end{bmatrix}$ the antidiagonal contains three primes (3,5,7).

etc...

Is there a matrix for n>1 that doesn't contain a prime in the antidiagonal?

Carlo Beenakker
  • 177,695
BennettLiam
  • 59
  • 1
    do you mean the anti-diagonal (rather than the diagonal)? Do you mean any square matrix ... looks like you have a particular form in mind? This question might have been more suitable for http://math.stackexchange.com/, along with an explanation what you have tried to solve this problem. – Mirko Jan 05 '16 at 01:39
  • 6
    The question seems to be whether there's always a prime among the numbers $n,2n-1,3n-2,\dots,n^2-n+1$. If that's off-topic, it's only because it's a notorious open problem, bounding the smallest prime in an arithmetic progression. – Gerry Myerson Jan 05 '16 at 02:17
  • 1
    I run a computer program, (using what @GerryMyerson also noted, for each $n$ checking the numbers $k\cdot n-k+1$,$k=1,2,\dots$ till a prime is found or $k>n$), so far the program always found a prime for $n$ up to $2508526$ and keeps running. – Mirko Jan 05 '16 at 02:25
  • I edited the question as it seems to have been intended and voted to reopen. – Brendan McKay Jan 05 '16 at 03:00
  • It is related to a theorem of Linnik as well as some open problems in the distribution of primes. I am willing to provide some detail in answer when the question gets reopened. Gerhard "Consider Other Lines Containing Primes" Paseman, 2016.01.04 – Gerhard Paseman Jan 05 '16 at 04:35
  • 6
    See http://mathoverflow.net/questions/217956/update-for-2015-least-prime-of-form-nq1-with-q-prime/217961#217961 which summarizes what is known. – Lucia Jan 05 '16 at 05:12
  • 1
    Here are the first few records for the first row with a prime:

    $$[2, 1], [4, 2], [8, 4], [18, 6], [20, 10], [60, 12], [160, 20], [228, 24], [318, 26], [362, 30],$$ $$[522, 32], [1638, 38], [1692, 42], [1998, 44], [2054, 46], [3834, 60], [5208, 84], [21210, 108],$$ $$[62810, 114], [152352, 126], [170168, 144], [424784, 166], [860832, 182]$$

     – Aaron Meyerowitz Jan 07 '16 at 03:02

2 Answers2

6

As suggested in the comments, this question is equivalent to asking for primes of the form 1 +kn, where (n+1) is given and k is an integer at most n+1. The current observations and theory suggest the answer is yes, for every n there is a k less than n+2 so that 1+kn is prime, but we do not have a proof. Linnik's theorem is mentioned in a question link provided in a comment of Lucia, and later results give conditional and unconditional bounds on k. Currently (as far as I know) your question is an open problem.

Much more can be said, however. The question is one of a class of problems of the location of primes in certain arrays. Two such problems are: is there a prime in every row of (a standard square arrangement of) a matrix of numbers from 1 to n^2 for every n > 1? Are there large connected components of primes in an Ulam spiral starting the spiral from any integer n? Your question inspires the following: How many diagonals (columns) contain primes in a (standard n by n) array? Is it always at least $2\phi(n) (\phi(n))$? Here one needs to nail down the definition of diagonal, but that is part of the fun of exploring. Other arrangements of numbers can be considered. As far as I know, hexagonal arrangements have been considered only for Eisenstein primes (cf Guy's UPINT book for more).

Gerhard "Opens Minds With Open Problems" Paseman, 2016.01.16

Gerhard Paseman
  • 12,968
  • One interesting approach, at least computationally speaking, is to list the larger half of the factors of p-1 and see how many primes p it takes to cover [1,n] with these factor sets. Gerhard "Attack Problems Through Conceptual Inversion" Paseman, 2016.01.16 – Gerhard Paseman Jan 16 '16 at 19:12
  • In fact, considering this approach shows that most (if not all) of the time, the first prime occurs in the upper half, as the required factor f usually satisfies ff is greater than 2p. This should be considered theoretically speaking as well. Gerhard "Computational Complexity Of Number Theory" Paseman, 2016.01.16. – Gerhard Paseman Jan 16 '16 at 19:23
  • To keep the answer brief, I left out many things, such as prime gaps, density results, and related questions. Tempting as it is to make stone soup, I couldn't just leave a wet rock alone. Gerhard "Gotta Have Some Hot Broth" Paseman, 2016.01.16 – Gerhard Paseman Jan 16 '16 at 19:34
1

While it may be hard to prove precise results, it is extremely likely that there are quite a lot of primes on this antidiagonal. If $a$ is an integer small relative to $n$, then the number of primes $p \equiv 1$ (mod $a$) with $p \leq n^{2}$ is of the order of $\frac{1}{\phi(a)}\frac{n^{2}}{\log n^{2}}$ for $n$ large enough. This is according to the quantitative version of Dirichlet's Theorem for primes in arithmetic progression, and is proved. Here we are looking at the case $a = n-1$ which is not small relative to $n$. Nevertheless, it would be interesting to compare the number of primes on the antidiagonal with

$$\left( \prod_{ {\rm prime} p | n-1} \frac{p}{p-1} \right) \frac{n}{2 \log n}$$ for $n$ large, and to examine the limiting behaviour of the ratio of the two quantities.

Geoff Robinson
  • 42,683