No Arabic abstract
We present a restricted variable generalization of Warnings Second Theorem (a result giving a lower bound on the number of solutions of a low degree polynomial system over a finite field, assuming one solution exists). This is analogous to Brinks restricted variable generalization of Chevalleys Theorem (a result giving conditions for a low degree polynomial system not to have exactly one solution). Just as Warnings Second Theorem implies Chevalleys Theorem, our result implies Brinks Theorem. We include several combinatorial applications, enough to show that we have a general tool for obtaining quantitative refinements of combinatorial existence theorems.
We present a short, self-contained, and purely combinatorial proof of Linniks theorem: for any $varepsilon > 0$ there exists a constant $C_varepsilon$ such that for any $N$, there are at most $C_varepsilon$ primes $p leqslant N$ such that the least positive quadratic non-residue modulo $p$ exceeds $N^varepsilon$.
Hegyvari and Hennecart showed that if $B$ is a sufficiently large brick of a Heisenberg group, then the product set $Bcdot B$ contains many cosets of the center of the group. We give a new, robust proof of this theorem that extends to all extra special groups as well as to a large family of quasigroups.
We give a short, self-contained proof of two key results from a paper of four of the authors. The first is a kind of weighted discrete Prekopa-Leindler inequality. This is then applied to show that if $A, B subseteq mathbb{Z}^d$ are finite sets and $U$ is a subset of a quasicube then $|A + B + U| geq |A|^{1/2} |B|^{1/2} |U|$. This result is a key ingredient in forthcoming work of the fifth author and Palvolgyi on the sum-product phenomenon.
Let $(R, mathfrak{m})$ be a complete discrete valuation ring with the finite residue field $R/mathfrak{m} = mathbb{F}_{q}$. Given a monic polynomial $P(t) in R[t]$ whose reduction modulo $mathfrak{m}$ gives an irreducible polynomial $bar{P}(t) in mathbb{F}_{q}[t]$, we initiate the investigation of the distribution of $mathrm{coker}(P(A))$, where $A in mathrm{Mat}_{n}(R)$ is randomly chosen with respect to the Haar probability measure on the additive group $mathrm{Mat}_{n}(R)$ of $n times n$ $R$-matrices. One of our main results generalizes two results of Friedman and Washington. Our other results are related to the distribution of the $bar{P}$-part of a random matrix $bar{A} in mathrm{Mat}_{n}(mathbb{F}_{q})$ with respect to the uniform distribution, and one of them generalizes a result of Fulman. We heuristically relate our results to a celebrated conjecture of Cohen and Lenstra, which predicts that given an odd prime $p$, any finite abelian $p$-group (i.e., $mathbb{Z}_{p}$-module) $H$ occurs as the $p$-part of the class group of a random imaginary quadratic field extension of $mathbb{Q}$ with a probability inversely proportional to $|mathrm{Aut}_{mathbb{Z}}(H)|$. We review three different heuristics for the conjecture of Cohen and Lenstra, and they are all related to special cases of our main conjecture, which we prove as our main theorems. For proofs, we use some concrete combinatorial connections between $mathrm{Mat}_{n}(R)$ and $mathrm{Mat}_{n}(mathbb{F}_{q})$ to translate our problems about a Haar-random matrix in $mathrm{Mat}_{n}(R)$ into problems about a random matrix in $mathrm{Mat}_{n}(mathbb{F}_{q})$ with respect to the uniform distribution.