Counting Polynomials via Galois Actions on Root Subsets

Or Ben-Porath · 2026

Read Counting Polynomials via Galois Actions on Root Subsets by Or Ben-Porath (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-14617.txt.

Introduction

Ben-Porath counts integer polynomials by the Galois action on their roots. The objects are monic polynomials with height at most H. Each count fixes a target permutation group for the root action. New upper bounds cover several group families. One family sits in wreath products with primitive action. Others act on k-subsets or k-tuples of the root set. Nearly all finite groups in regular form are handled as well. The bounds sharpen what counting by Galois type can say.

Catalog record

CREATOROr Ben-Porath
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38967
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14617

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Counting Polynomials via Galois Actions on Root Subsets Or Ben-Porath Abstract . This paper studies the number of monic integer polynomials f f of height at most H H whose Galois group, endowed with the action on the roots, is isomorphic to a prescribed permutation group ( G , Ω ) (G,\Omega) . New upper bounds are obtained for several families of groups: transitive subgroups of the wreath product S m ≀ S r S_{m}\wr S_{r} in the primitive action; k k -homogeneous subgroups of S m S_{m} in the action on k k -subsets of { 1 , … , m } \{1,\ldots,m\} ; k k -transitive subgroups of S m S_{m} in the action on k k -tuples of distinct elements of { 1 , … , m } \{1,\ldots,m\} . Almost all finite groups in their regular permutation representation are also treated. 2020 Mathematics Subject Classification Primary 11R32, 11R09; Secondary 11R45, 20B05 1. Introduction Probabilistic Galois theory studies the distribution of Galois groups of random algebraic objects. A central instance is the large box model, where one considers monic integer polynomials of fixed degree and growing height. A finite group G acting faithfully on a finite set \Omega is called a permutation group and denoted by (G,\Omega) . Denote the height of a polynomial f=\sum_{i}a_{i}x^{i}\in\mathbb{Z}[x] by H(f)=\max_{i}|a_{i}| . For n\in\mathbb{N} and H\geq 1 , set \displaystyle B_{n}(H) \displaystyle:=\{f\in\mathbb{Z}[x]:f\textnormal{ monic},\deg f=n,H(f)\leq H\}, \displaystyle b_{n}(H) \displaystyle:=|B_{n}(H)|=(2\lfloor H\rfloor+1)^{n}\sim(2H)^{n}. To each separable f\in B_{n}(H) attach the permutation group (G_{f},\Omega_{f}) , where \Omega_{f}:=\{\alpha\in\mathbb{C}:f(\alpha)=0\},\quad G_{f}:=\Gal\bigl(\mathbb{Q}(\Omega_{f})/\mathbb{Q}\bigr), and G_{f} acts on \Omega_{f} naturally. Given a finite permutation group (G,\Omega) , denote B(H;G,\Omega):=\{f\in B_{|\Omega|}(H):(G_{f},\Omega_{f})\cong(G,\Omega)\}. Write [n]:=\{1,\ldots,n\} . Hilbert’s irreducibility theorem implies that \left|B(H;S_{n},[n])\right|\sim b_{n}(H). For n\geq 3 , Chela [ 6 ] proved that \left|\{f\in B_{n}(H):f\text{ reducible}\}\right|\sim\left|B(H;S_{n-1},[n])\right|\sim c_{n}H^{n-1}, for an explicit constant c_{n} . Van der Waerden [ 15 ] conjectured that \left|\{f\in B_{n}(H):(G_{f},\Omega_{f})\not\cong(S_{n},[n])\}\right|\sim\left|B(H;S_{n-1},[n])\right|. Progress towards this conjecture was made in a series of subsequent works [ 10 , 9 , 16 , 8 , 7 , 1 ] . Finally, Bhargava [ 4 , Theorem 1] proved the conjecture up to a constant, by showing that \left|B(H;G,[n])\right|\ll H^{n-1} for every proper subgroup G<S_{n} . In this paper we obtain new upper bounds on \left|B(H;G,\Omega)\right| for several families of permutation groups (G,\Omega) . Primitive wreath product actions Let m,r,k\in\mathbb{N} with m\geq 2 , k\leq m/2 , and (r,k)\neq(1,1) . Set \binom{[m]}{k}:=\{A\subset[m]:|A|=k\},\qquad\Omega^{P}(m,r,k):=\binom{[m]}{k}^{r}, so that elements of \binom{[m]}{k} are k -subsets of [m] , and elements of \Omega^{P}(m,r,k) are r -tuples of k -subsets of [m] . Put n:=|\Omega^{P}(m,r,k)|=\binom{m}{k}^{r} . The wreath product S_{m}\wr S_{r} (see Definition 2.2 ) acts naturally on \Omega^{P}(m,r,k) in its primitive action (see Definition 2.3 ). Following [ 4 ] we call a transitive subgroup of (S_{m}\wr S_{r},\Omega^{P}(m,r,k)) a primitive non-elemental permutation group of type (r,m,k) . Bhargava [ 4 , Corollary 3] proved that for every primitive non-elemental permutation group G of type (r,m,k) , (1) \left|B(H;G,\Omega^{P}(m,r,k))\right|\ll H^{c\sqrt{n}(\log n)^{2}}=H^{c\binom{m}{k}^{r/2}r^{2}\log^{2}\binom{m}{k}}, for some absolute constant c . Our first result improves this bound for r>1 . Theorem 1.1 . Fix \epsilon>0 , integers m,r\geq 2 , and 1\leq k\leq m/2 . Let G\leq S_{m}\wr S_{r} be a primitive non-elemental permutation group of type (r,m,k) . Then (2) \left|B(H;G,\Omega^{P}(m,r,k))\right|\ll H^{r\left(\binom{m}{k}+r-1\right)+1+\epsilon}. We compare the exponents e_{1} and e_{2} of H in ( 1 ) and ( 2 ), respectively. Since \binom{m}{k}=n^{1/r} and r=\log_{\binom{m}{k}}n\leq\log_{2}n , e_{2}=r\left(\binom{m}{k}+r-1\right)+1+\epsilon\ll n^{1/r}\log n+(\log n)^{2}. In particular, \frac{e_{1}}{e_{2}}\gg\frac{\sqrt{n}(\log n)^{2}}{n^{1/r}\log n+(\log n)^{2}}\gg\begin{cases}\log n,&r=2,\\ n^{1/2-1/r},&r>2.\end{cases} Hence, for n sufficiently large, ( 2 ) is sharper than ( 1 ). k -homogeneous and k -transitive actions Primitive non-elemental permutation groups of type (1,m,k) are subgroups G\leq S_{m} acting transitively on k -subsets of [m] , which are classically called k -homogeneous groups. Specializing ( 1 ) to r=1 gives (3) \left|B\left(H;G,\binom{[m]}{k}\right)\right|\ll H^{c\binom{m}{k}^{1/2}\log^{2}\binom{m}{k}}. Since (S_{m},\binom{[m]}{k})\cong(S_{m},\binom{[m]}{m-k}) via the complement map, there is no loss of generality in assuming k\leq m/2 . Our next result improves this bound. Theorem 1.2 . Fix \epsilon>0 and 1\leq k\leq m/2 . Let G\leq S_{m} be k -homogeneous. Then (4) \left|B\left(H;G,\binom{[m]}{k}\right)\right|\ll H^{mk+1+\epsilon}. For k=1 , the bound is immediate since \left|B(H;G,[m])\right|\leq b_{m}(H)\asymp H^{m} . We compare the exponents e_{3} and e_{4} of H in ( 3 ) and ( 4 ), respectively. Using the well-known bound \binom{m}{k}\geq(m/k)^{k} , \frac{e_{3}}{e_{4}}\gg\frac{(m/k)^{k/2}\cdot k^{2}\log^{2}(m/k)}{mk}=(m/k)^{k/2-1}\log^{2}(m/k), Hence, for m sufficiently large and any 2\leq k\leq m/2 , ( 4 ) is sharper than ( 3 ). We next consider k -transitive actions, a strengthening of k -homogeneity. For m\geq 2 and 1\leq k\leq m , let [m]_{k}:=\{(v_{1},\ldots,v_{k})\in[m]^{k}:v_{i}\neq v_{j}\text{ for }i\neq j\} denote the set of k -tuples of distinct elements of [m] . Its cardinality is the falling factorial (m)_{k}=\frac{m!}{(m-k)!} . The symmetric group S_{m} acts on [m]_{k} coordinatewise. A subgroup G\leq S_{m} is called k -transitive if it acts transitively on [m]_{k} . Clearly, a k -transitive subgroup of S_{m} is also k -homogeneous. In the other direction, by [ 12 , Theorem 2] , for k\leq m/2 , every k -homogeneous subgroup of S_{m} is (k-1) -transitive. Theorem 1.3 . Fix \epsilon>0 and 1\leq k\leq m . Let G\leq S_{m} be k -transitive. Then \left|B(H;G,[m]_{k})\right|\ll H^{m+1+\epsilon}. For k=1 , Theorem 1.3 is immediate, as \left|B(H;G,[m])\right|\leq b_{m}(H)\asymp H^{m} . The case m=k=2 is similarly immediate, as \left|B(H;G,[2]_{2})\right|\leq b_{2}(H)\asymp H^{2} . We are unaware of previous bounds specific to \left|B(H;G,[m]_{k})\right| for k -transitive groups. For any k\geq 2 , since G is a proper transitive subgroup of S_{(m)_{k}} , Bhargava [ 4 , Theorem 1] gives (5) \left|B(H;G,[m]_{k})\right|\ll H^{(m)_{k}-1}. For any m\geq 3 and k\geq 2 , Theorem 1.3 gives a sharper bound than ( 5 ). We note that the classification of finite simple groups implies that, other than A_{m} and S_{m} , there are no k -transitive (hence k -homogeneous) subgroups of S_{m} for k larger than some absolute constant. Nevertheless, Theorems 1.2 and 1.3 are not vacuous in this regime, as they give new bounds for |B(H;G,\binom{[m]}{k})| and |B(H;G,[m]_{k})| for G=A_{m},S_{m} . Regular actions Recall that a permutation group (G,\Omega) is called regular if the action is transitive and |G|=|\Omega| . In this case (G,\Omega)\cong(G,G) , where G acts on itself by left multiplication. Bhargava [ 4 , Corollary 6] proved that for every regular permutation group (G,\Omega) , (6) \left|B(H;G,\Omega)\right|\ll H^{\frac{3|G|}{11}+1.164}. Since S_{m} is m -transitive and |[m]_{m}|=(m)_{m}=m! , the permutation group (S_{m},[m]_{m}) is regular. Theorem 1.3 then gives \left|B(H;S_{m},[m]_{m})\right|\ll H^{m+1+\epsilon}, whereas ( 6 ) only gives \left|B(H;S_{m},[m]_{m})\right|\ll H^{\frac{3m!}{11}+1.164}. For a finite group G , let \mu(G) denote the minimal faithful permutation degree of G , that is, \mu(G):=\min\{m\in\mathbb{N}:G\textnormal{ admits a faithful action on an }m\textnormal{-set}\}. The following theorem generalizes the bound for (S_{m},[m]_{m}) to all regular actions. Theorem 1.4 . Fix \epsilon>0 . Let (G,\Omega) be a regular permutation group with minimal faithful permutation degree \mu=\mu(G) . Then (7) \left|B(H;G,\Omega)\right|\ll H^{\mu+1+\epsilon}. We compare the exponents of H in ( 6 ) and ( 7 ). Let \iota(G) denote the minimal index of a cyclic subgroup of prime-power order in G . Babai, Goodman and Pyber [ 2 , Theorem 1.1] proved that there exists a function \psi with \psi(n)\to\infty as n\to\infty such that \mu(G)\leq\frac{|G|}{\psi\bigl(\iota(G)\bigr)}, for every finite group G . In particular, there exists an absolute constant C such that \mu(G)<\frac{3|G|}{11} , unless G

Read the complete text