More Like this

1. VC-Dimension of Hyperplanes Over Finite Fields

   https://doi.org/10.1007/s00373-025-02909-6  

   Ascoli, Ruben; Betti, Livia; Cheigh, Justin; Iosevich, Alex; Jeong, Ryan; Liu, Xuyan; McDonald, Brian; Milgrim, Wyatt; Miller, Steven_J; Romero_Acosta, Francisco; et al (March 2025, Graphs and Combinatorics)

   Abstract Let$$\mathbb {F}_q^d$$ $F_q^d$be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$and a fixed nonzero$$t\in \mathbb {F}_q$$ $t\in F_q$, let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ $H_t\left(E\right)=\{h_y:y\in E\}$, where$$h_y:E\rightarrow \{0,1\}$$ $h_y:E\to \{0,1\}$is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ $\{x\in E:x·y=t\}$. Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ $d=3$that if$$|E|\ge Cq^{\frac{11}{4}}$$ $\left|E\right|\ge C{q}^{\frac{11}{4}}$andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ $H_t\left(E\right)$isdwhenever$$E\subseteq \mathbb {F}_q^d$$ $E\subseteq F_q^d$with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ $\left|E\right|\ge C_d{q}^{d-\frac{1}{d-1}}$. 

   more » « less
2. Products of primes in arithmetic progressions

   https://doi.org/10.1515/crelle-2023-0096  

   Matomäki, Kaisa; Teräväinen, Joni (January 2024, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract A conjecture of Erdős states that, for any large primeq, every reduced residue class $\left(\mathrm{mod}q\right)${(\operatorname{mod}q)}can be represented as a product $p_1{p}_2${p_{1}p_{2}}of two primes $p_1,p_2\le q${p_{1},p_{2}\leq q}. We establish a ternary version of this conjecture, showing that, for any sufficiently large cube-free integerq, every reduced residue class $\left(\mathrm{mod}q\right)${(\operatorname{mod}q)}can be written as $p_1{p}_2{p}_3${p_{1}p_{2}p_{3}}with $p_1,p_2,p_3\le q${p_{1},p_{2},p_{3}\leq q}primes. We also show that, for any $\epsilon >0${\varepsilon>0}and any sufficiently large integerq, at least $\left(\frac{2}{3}-\epsilon \right)\phi \left(q\right)${(\frac{2}{3}-\varepsilon)\varphi(q)}reduced residue classes $\left(\mathrm{mod}q\right)${(\operatorname{mod}q)}can be represented as a product $p_1{p}_2${p_{1}p_{2}}of two primes $p_1,p_2\le q${p_{1},p_{2}\leq q}.The problems naturally reduce to studying character sums. The main innovation in the paper is the establishment of a multiplicative dense model theorem for character sums over primes in the spirit of the transference principle. In order to deal with possible local obstructions we establish bounds for the logarithmic density of primes in certain unions of cosets of subgroups of ${\mathbb{Z}}_q^{\times }${\mathbb{Z}_{q}^{\times}}of small index and study in detail the exceptional case that there exists a quadratic character $\psi \left(\mathrm{mod}q\right)${\psi~{}(\operatorname{mod}\,q)}such that $\psi \left(p\right)=-1${\psi(p)=-1}for very many primes $p\le q${p\leq q}. 

   more » « less
3. Abelian varieties of prescribed order over finite fields

   https://doi.org/10.1007/s00208-024-03084-4  

   van_Bommel, Raymond; Costa, Edgar; Li, Wanlin; Poonen, Bjorn; Smith, Alexander (March 2025, Mathematische Annalen)

   Abstract Given a prime powerqand$$n \gg 1$$ $n\gg 1$, we prove that every integer in a large subinterval of the Hasse–Weil interval$$[(\sqrt{q}-1)^{2n},(\sqrt{q}+1)^{2n}]$$ $[{(\sqrt{q}-1)}^{2n},{(\sqrt{q}+1)}^{2n}]$is$$\#A({\mathbb {F}}_q)$$ $\#A\left(F_q\right)$for some ordinary geometrically simple principally polarized abelian varietyAof dimensionnover$${\mathbb {F}}_q$$ $F_q$. As a consequence, we generalize a result of Howe and Kedlaya for$${\mathbb {F}}_2$$ $F_2$to show that for each prime powerq, every sufficiently large positive integer is realizable, i.e.,$$\#A({\mathbb {F}}_q)$$ $\#A\left(F_q\right)$for some abelian varietyAover$${\mathbb {F}}_q$$ $F_q$. Our result also improves upon the best known constructions of sequences of simple abelian varieties with point counts towards the extremes of the Hasse–Weil interval. A separate argument determines, for fixedn, the largest subinterval of the Hasse–Weil interval consisting of realizable integers, asymptotically as$$q \rightarrow \infty $$ $q\to \infty$; this gives an asymptotically optimal improvement of a 1998 theorem of DiPippo and Howe. Our methods are effective: We prove that if$$q \le 5$$ $q\le 5$, then every positive integer is realizable, and for arbitraryq, every positive integer$$\ge q^{3 \sqrt{q} \log q}$$ $\ge q^{3\sqrt{q}logq}$is realizable. 

   more » « less
4. Towards a Schinzel–Wójcik theorem for number fields

   https://doi.org/10.1007/s40879-025-00819-8  

   Pollack, Paul (April 2025, European Journal of Mathematics)

   Abstract Schinzel and Wójcik have shown that for every$$\alpha ,\beta \in \mathbb {Q}^{\times }\hspace{0.55542pt}{\setminus }\hspace{1.111pt}\{\pm 1\}$$ $\alpha ,\beta \in Q^{\times }\backslash \{\pm 1\}$, there are infinitely many primespwhere$$v_p(\alpha )=v_p(\beta )=0$$ $v_p\left(\alpha \right)=v_p\left(\beta \right)=0$and where$$\alpha $$ $\alpha$and$$\beta $$ $\beta$generate the same multiplicative group modp. We prove a weaker result in the same direction for algebraic numbers$$\alpha , \beta $$ $\alpha ,\beta$. Let$$\alpha , \beta \in \overline{\mathbb {Q}} ^{\times }$$ $\alpha ,\beta \in {\overline{Q}}^{\times }$, and suppose$$|N_{\mathbb {Q}(\alpha ,\beta )/\mathbb {Q}}(\alpha )|\ne 1$$ $|N_{Q(\alpha ,\beta )/Q}\left(\alpha \right)|\ne 1$and$$|N_{\mathbb {Q}(\alpha ,\beta )/\mathbb {Q}}(\beta )|\ne 1$$ $|N_{Q(\alpha ,\beta )/Q}\left(\beta \right)|\ne 1$. Then for some positive integer$$C = C(\alpha ,\beta )$$ $C=C(\alpha ,\beta )$, there are infinitely many prime idealsPof Equation missing<#comment/>where$$v_P(\alpha )=v_P(\beta )=0$$ $v_P\left(\alpha \right)=v_P\left(\beta \right)=0$and where the group$$\langle \beta \bmod {P}\rangle $$ $⟨\beta modP⟩$is a subgroup of$$\langle \alpha \bmod {P}\rangle $$ $⟨\alpha modP⟩$with$$[\langle \alpha \bmod {P}\rangle \,{:}\, \langle \beta \bmod {P}\rangle ]$$ $[⟨\alpha modP⟩:⟨\beta modP⟩]$dividingC. A key component of the proof is a theorem of Corvaja and Zannier bounding the greatest common divisor of shiftedS-units. 

   more » « less
5. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József; Clemen, Felix Christian; Dumitrescu, Adrian (September 2024, Algorithmica)

   Abstract LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$ ${[0,1]}^k$where$$k \ge 2$$ $k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$ $x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$ $|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$ $c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$ $x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$ $k\ge 2$and$$n \ge 2$$ $n\ge 2$, there existnpoints in$$[0,1]^k$$ ${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$ ${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$ $c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$ $k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$ $c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$ $k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$ $c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$ $c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$ $c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$ $k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed. 

   more » « less