ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let AA be an ϵ\epsilon-balanced random integer matrix of size n×(1+δ)nn\times(1+\delta)n, where ϵ,δ>0\epsilon,\delta>0 are constants, and suppose that its entries are bounded in absolute value by nkn^k for some constant k>0k>0. Regard AA as a homomorphism Z(1+δ)n→Zn\mathbb{Z}^{(1+\delta)n}\to\mathbb{Z}^n.

Rectangular surjectivity conjecture. Then

lim⁡n→∞P(A is surjective)=1.\lim_{n\to\infty}\mathbb{P}(A\text{ is surjective})=1.

The paper proves exponential-probability surjectivity when the number of columns is (2+δ)n(2+\delta)n and conjectures that the same qualitative conclusion holds with only (1+δ)n(1+\delta)n columns, under polynomial entry bounds and the balancedness hypothesis.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.