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
    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
    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
    Jan 5, 2016 at 2:25
  • 6
    $\begingroup$ See mathoverflow.net/questions/217956/… which summarizes what is known. $\endgroup$
    – Lucia
    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
    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
    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
    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
    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
    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
    Jan 23, 2016 at 12:33

Your Answer

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

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