5
$\begingroup$

I found a very interesting problem in the Open Problem Garden, which I am surprised is not as well-known as I would think it would be:

Prove that If $p>3$ is prime and $A$ is an invertible $n \times n$ matrix with entries in ${\mathbb Z_p}$, then there are column vectors $x,y \in {\mathbb Z_p}^n$ which have no coordinates equal to zero such that $Ax=y$.

It is easy to show that this conjecture is false when $p=2,3$. Also, when $p$ is a little larger than $n$, this conjecture has been proven true. However, the case when $n$ is large relative to $p$ seems not only difficult to prove, but also it seems to require nontrivial computational resources to even get a sense of what is going on.

Has any work been done to try to computationally understand this problem? In particular, is this conjecture known to be true for say $p=5$, $n=15$?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is the Alon-Jaeger-Tarsi conjecture first stated in 1981 and resolved very recently (for $p\ge 83$) by János Nagy and Péter Pál Pach.

$\endgroup$

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.