5
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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 math.stackexchange.com, along with an explanation what you have tried to solve this problem. $\endgroup$
    – Mirko
    Commented Jan 5, 2016 at 1:39
  • 6
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Jan 5, 2016 at 2:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mirko
    Commented Jan 5, 2016 at 2:25
  • 6
    $\begingroup$ See mathoverflow.net/questions/217956/… which summarizes what is known. $\endgroup$
    – Lucia
    Commented Jan 5, 2016 at 5:12
  • 1
    $\begingroup$ 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]$$ $\endgroup$
    – Aaron Meyerowitz
    Commented Jan 7, 2016 at 3:02

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jan 16, 2016 at 19:12
  • $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Jan 16, 2016 at 19:23
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jan 16, 2016 at 19:34
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you for bringing up a potential density result. Gerhard "Loves Seeing Crowdsourced Mathematics Grow" Paseman, 2016.01.22. $\endgroup$
    – Gerhard Paseman
    Commented Jan 22, 2016 at 16:11
  • $\begingroup$ I revised some earlier comments I made in light of the reaction they got.I would like to see how the numbers work. $\endgroup$
    – Geoff Robinson
    Commented Jan 23, 2016 at 12:33

You must log in to answer this question.

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