Title: VC-Dimension of Hyperplanes Over Finite Fields
Abstract Let$$\mathbb {F}_q^d$$ Fqd be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ E⊆Fqd and a fixed nonzero$$t\in \mathbb {F}_q$$ t∈Fq , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ Ht(E)= {hy:y∈E} , where$$h_y:E\rightarrow \{0,1\}$$ hy:E→{0,1} is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ {x∈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}}$$ |E|≥Cq114 andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ Ht(E) is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ Ht(E) isdwhenever$$E\subseteq \mathbb {F}_q^d$$ E⊆Fqd with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ |E|≥Cdq d- 1d-1 .  more » « less
Award ID(s):
2241623 2154232
PAR ID:
10580626
Author(s) / Creator(s):
; ; ; ; ; ; ; ; ; ;
Publisher / Repository:
Springer
Date Published:
Journal Name:
Graphs and Combinatorics
Volume:
41
Issue:
2
ISSN:
0911-0119
Subject(s) / Keyword(s):
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract For the partition functionp(n), Ramanujan proved the striking identities$$\begin{aligned} \begin{aligned} \mathcal {P}_5(q):=\sum _{n\ge 0} p(5n+4)q^n&=5\prod _{n\ge 1} \frac{\left( q^5;q^5\right) _{\infty }^5}{(q;q)_{\infty }^6},\\ \mathcal {P}_{7}(q):=\sum _{n\ge 0} p(7n+5)q^n&=7\prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^3}{(q;q)_{\infty }^4}+49q \prod _{n\ge 1}\frac{\left( q^7;q^7\right) _{\infty }^7}{(q;q)_{\infty }^8}, \end{aligned} \end{aligned}$$ P5(q):= ∑n≥0 p(5n+4)qn =5 ∏n≥1 q5;q5∞5 (q;q)∞6 , P7(q):= ∑n≥0 p(7n+5)qn =7 ∏n≥1 q7;q7∞3 (q;q)∞4 +49q ∏n≥1 q7;q7∞7 (q;q)∞8 , where$$(q;q)_{\infty }:=\prod _{n\ge 1}(1-q^n).$$ (q;q)∞ := ∏n≥1 (1-qn). As these identities imply his celebrated congruences modulo 5 and 7, it is natural to seek, for primes$$\ell \ge 5,$$ ℓ≥5, closed form expressions of the power series$$ \mathcal {P}_{\ell }(q):=\sum _{n\ge 0} p(\ell n-\delta _{\ell })q^n\pmod {\ell }, $$ Pℓ(q):= ∑n≥0 p (ℓn-δℓ) qn (modℓ) , where$$\delta _{\ell }:=\frac{\ell ^2-1}{24}.$$ δℓ:= ℓ2-124 . In this paper, we prove that$$ \mathcal {P}_{\ell }(q)\equiv c_{\ell } \dfrac{\mathcal {T}_{\ell }(q)}{\left( q^\ell ; q^\ell \right) _\infty } \pmod {\ell }, $$ Pℓ(q)≡cℓ Tℓ(q) qℓ;qℓ∞ (modℓ) , where$$c_{\ell }\in \mathbb Z$$ cℓ∈Z is explicit and$${\mathcal {T}}_{\ell }(q)$$ Tℓ(q) is the generating function for the Hecke traces of$$\ell $$ ℓ -ramified values of special Dirichlet series for weight$$\ell -1$$ ℓ-1 cusp forms on$$\textrm{SL}_2(\mathbb Z)$$ SL2(Z) . This is a new proof of Ramanujan’s congruences modulo 5, 7, and 11, as there are no nontrivial cusp forms of weight 4, 6, and 10. 
    more » « less
  2. Abstract Fix a positive integernand a finite field$${\mathbb {F}}_q$$ Fq . We study the joint distribution of the rank$${{\,\mathrm{rk}\,}}(E)$$ rk (E) , then-Selmer group$$\text {Sel}_n(E)$$ Seln(E) , and then-torsion in the Tate–Shafarevich group Equation missing<#comment/>asEvaries over elliptic curves of fixed height$$d \ge 2$$ d≥2 over$${\mathbb {F}}_q(t)$$ Fq(t) . We compute this joint distribution in the largeqlimit. We also show that the “largeq, then large height” limit of this distribution agrees with the one predicted by Bhargava–Kane–Lenstra–Poonen–Rains. 
    more » « less
  3. Abstract We study the shifted convolution problem for the divisor function in function fields in the large degree limit, that is, the average value of$$d(f) d(f+h)$$ d(f)d(f+h) wherefruns over monic polynomials in$$\mathbb {F}_q[T]$$ Fq[T] of a given degree, andhis a given monic polynomial. We prove an asymptotic formula in the range$$\deg (h) < (2-\epsilon )\deg (f)$$ deg(h)<(2-ϵ)deg(f) . We also consider mixed correlations and self-correlations of$$r_\chi = 1 \star \chi $$ rχ=1⋆χ , the convolution of 1 with a Dirichlet character mod$$\ell $$ ℓ , where$$\ell $$ ℓ is a monic irreducible polynomial, proving asymptotic formulae in various ranges. This includes the case of quadratic characters, which yields results about correlations of norm-counting functions of quadratic extensions of$$\mathbb {F}_q[T]$$ Fq[T] . A novel feature of our work is a Voronoi summation formula (equivalently, a functional equation for the Estermann function) in$$\mathbb {F}_q[T]$$ Fq[T] which was not previously available. 
    more » « less
  4. Abstract Given a prime powerqand$$n \gg 1$$ n≫1 , we prove that every integer in a large subinterval of the Hasse–Weil interval$$[(\sqrt{q}-1)^{2n},(\sqrt{q}+1)^{2n}]$$ [ (q-1) 2n , (q+1) 2n ] is$$\#A({\mathbb {F}}_q)$$ #A(Fq) for some ordinary geometrically simple principally polarized abelian varietyAof dimensionnover$${\mathbb {F}}_q$$ Fq . As a consequence, we generalize a result of Howe and Kedlaya for$${\mathbb {F}}_2$$ F2 to show that for each prime powerq, every sufficiently large positive integer is realizable, i.e.,$$\#A({\mathbb {F}}_q)$$ #A(Fq) for some abelian varietyAover$${\mathbb {F}}_q$$ Fq . 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→∞ ; 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≤5 , then every positive integer is realizable, and for arbitraryq, every positive integer$$\ge q^{3 \sqrt{q} \log q}$$ ≥q 3qlogq is realizable. 
    more » « less
  5. Abstract Motivated by problems in control theory concerning decay rates for the damped wave equation$$\begin{aligned} w_{tt}(x,t) + \gamma (x) w_t(x,t) + (-\Delta + 1)^{s/2} w(x,t) = 0, \end{aligned}$$ wtt (x,t)+γ(x)wt(x,t)+(-Δ+1)s/2w(x,t)=0, we consider an analogue of the classical Paneah-Logvinenko-Sereda theorem for the Fourier Bessel transform. In particular, if$$E \subset \mathbb {R}^+$$ E⊂R+ is$$\mu _\alpha $$ μα -relatively dense (where$$d\mu _\alpha (x) \approx x^{2\alpha +1}\, dx$$ dμα(x)≈x2α+1dx ) for$$\alpha > -1/2$$ α>-1/2 , and$$\operatorname {supp} \mathcal {F}_\alpha (f) \subset [R,R+1]$$ suppFα(f)⊂[R,R+1] , then we show$$\begin{aligned} \Vert f\Vert _{L^2_\alpha (\mathbb {R}^+)} \lesssim \Vert f\Vert _{L^2_\alpha (E)}, \end{aligned}$$ ‖f‖ Lα2(R+) ≲ ‖f‖ Lα2(E) , for all$$f\in L^2_\alpha (\mathbb {R}^+)$$ f∈Lα2(R+) , where the constants in$$\lesssim $$ ≲ do not depend on$$R > 0$$ R>0 . Previous results on PLS theorems for the Fourier-Bessel transform by Ghobber and Jaming (2012) provide bounds that depend onR. In contrast, our techniques yield bounds that are independent ofR, offering a new perspective on such results. This result is applied to derive decay rates of radial solutions of the damped wave equation. 
    more » « less