An official website of the United States government
We investigate k-superirreducible polynomials, by which we mean irreducible polynomials that remain irreducible under any polynomial substitution of positive degree at most k. Let F be a finite field of characteristic p. We show that no 2-superirreducible polynomials exist in F[t] when p=2 and that no such polynomials of odd degree exist when p is odd. We address the remaining case in which p is odd and the polynomials have even degree by giving an explicit formula for the number of monic 2-superirreducible polynomials having even degree d. This formula is analogous to that given by Gauss for the number of monic irreducible polynomials of given degree over a finite field. We discuss the associated asymptotic behaviour when either the degree of the polynomial or the size of the finite field tends to infinity.
more »
« less
Quantitative Hilbert Irreducibility and Almost Prime Values of Polynomial Discriminants
Abstract We study two polynomial counting questions in arithmetic statistics via a combination of Fourier analytic and arithmetic methods. First, we obtain new quantitative forms of Hilbert’s Irreducibility Theorem for degree $$n$$ polynomials $$f$$ with $$\textrm {Gal}(f) \subseteq A_n$$. We study this both for monic polynomials and non-monic polynomials. Second, we study lower bounds on the number of degree $$n$$ monic polynomials with almost prime discriminants, as well as the closely related problem of lower bounds on the number of degree $$n$$ number fields with almost prime discriminants.
more »
« less
- PAR ID:
- 10406227
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- Volume:
- 2023
- Issue:
- 3
- ISSN:
- 1073-7928
- Page Range / eLocation ID:
- 2188 to 2214
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We consider negative moments of quadratic Dirichlet $$L$$–functions over function fields. Summing over monic square-free polynomials of degree $2g+1$ in $$\mathbb{F}_{q}[x]$$, we obtain an asymptotic formula for the $$k^{\textrm{th}}$$ shifted negative moment of $$L(1/2+\beta ,\chi _{D})$$, in certain ranges of $$\beta $$ (e.g., when roughly $$\beta \gg \log g/g $$ and $k<1$). We also obtain non-trivial upper bounds for the $$k^{\textrm{th}}$$ shifted negative moment when $$\log (1/\beta ) \ll \log g$$. Previously, almost sharp upper bounds were obtained in [ 3] in the range $$\beta \gg g^{-\frac{1}{2k}+\epsilon }$$.more » « less
-
Raz, Ran (Ed.)We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem.more » « less
-
Abstract For every integer k there exists a bound $$B=B(k)$$ B = B ( k ) such that if the characteristic polynomial of $$g\in \textrm{SL}_n(q)$$ g ∈ SL n ( q ) is the product of $$\le k$$ ≤ k pairwise distinct monic irreducible polynomials over $$\mathbb {F}_q$$ F q , then every element x of $$\textrm{SL}_n(q)$$ SL n ( q ) of support at least B is the product of two conjugates of g . We prove this and analogous results for the other classical groups over finite fields; in the orthogonal and symplectic cases, the result is slightly weaker. With finitely many exceptions ( p , q ), in the special case that $$n=p$$ n = p is prime, if g has order $$\frac{q^p-1}{q-1}$$ q p - 1 q - 1 , then every non-scalar element $$x \in \textrm{SL}_p(q)$$ x ∈ SL p ( q ) is the product of two conjugates of g . The proofs use the Frobenius formula together with upper bounds for values of unipotent and quadratic unipotent characters in finite classical groups.more » « less
-
An integer is called almost-prime if it has fewer than a fixed number of prime factors. In this paper, we study the asymptotic distribution of almost-prime entries in horospherical flows on Gamma\SL(n,R), where Gamma is either SL(n,Z) or a cocompact lattice. In the cocompact case, we obtain a result that implies density for almost-primes in horospherical flows where the number of prime factors is independent of basepoint, and in the space of lattices we show the density of almost-primes in abelian horospherical orbits of points satisfying a certain Diophantine condition. Along the way we give an effective equidistribution result for arbitrary horospherical flows on the space of lattices, as well as an effective rate for the equidistribution of arithmetic progressions in abelian horospherical flows.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnab296
