skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: VC-Dimension of Hyperplanes Over Finite Fields
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 F q d and a fixed nonzero$$t\in \mathbb {F}_q$$ t F q , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ H t ( E ) = { h y : y E } , where$$h_y:E\rightarrow \{0,1\}$$ h y : 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 | C q 11 4 andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) 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 ( E ) isdwhenever$$E\subseteq \mathbb {F}_q^d$$ E F q d with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ | E | C d q d - 1 d - 1 more » « less
Award ID(s):
2241623 2154232
PAR ID:
10577551
Author(s) / Creator(s):
; ; ; ; ; ; ; ; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Graphs and Combinatorics
Volume:
41
Issue:
2
ISSN:
0911-0119
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Fix a positive integernand a finite field$${\mathbb {F}}_q$$ F q . We study the joint distribution of the rank$${{\,\mathrm{rk}\,}}(E)$$ rk ( E ) , then-Selmer group$$\text {Sel}_n(E)$$ Sel n ( 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)$$ F q ( 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
  2. 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 ) 2 n , ( q + 1 ) 2 n ] is$$\#A({\mathbb {F}}_q)$$ # A ( F q ) 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 ( F q ) 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 ; 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 3 q log q is realizable. 
    more » « less
  3. Abstract Let$$(h_I)$$ ( h I ) denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ I D , the set of dyadic intervals and$$h_I\otimes h_J$$ h I h J denote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$ ( s , t ) h I ( s ) h J ( t ) ,$$I,J\in \mathcal {D}$$ I , J D . We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$ V ( δ 2 ) of$$h_I\otimes h_J$$ h I h J ,$$I,J\in \mathcal {D}$$ I , J D . This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$ L p [ 0 , 1 ] or the Hardy spaces$$H^p[0,1]$$ H p [ 0 , 1 ] ,$$1\le p < \infty $$ 1 p < . We say that$$D:X(Y)\rightarrow X(Y)$$ D : X ( Y ) X ( Y ) is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$ D ( h I h J ) = d I , J h I h J , where$$d_{I,J}\in \mathbb {R}$$ d I , J R , and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ C : V ( δ 2 ) V ( δ 2 ) given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ C h I h J = h I h J if$$|I|\le |J|$$ | I | | J | , and$$\mathcal {C} h_I\otimes h_J = 0$$ C h I h J = 0 if$$|I| > |J|$$ | I | > | J | , as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$ D : X ( Y ) X ( Y ) , there exist$$\lambda ,\mu \in \mathbb {R}$$ λ , μ R such that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$ λ C + μ ( Id - C ) approximately 1-projectionally factors through D , i.e., for all$$\eta > 0$$ η > 0 , there exist bounded operatorsA, Bso thatABis the identity operator$${{\,\textrm{Id}\,}}$$ Id ,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ A · B = 1 and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$ λ C + μ ( Id - C ) - A D B < η . Additionally, if$$\mathcal {C}$$ C is unbounded onX(Y), then$$\lambda = \mu $$ λ = μ and then$${{\,\textrm{Id}\,}}$$ Id either factors throughDor$${{\,\textrm{Id}\,}}-D$$ Id - D
    more » « less
  4. A<sc>bstract</sc> We develop Standard Model Effective Field Theory (SMEFT) predictions ofσ($$ \mathcal{GG} $$ GG →h), Γ(h→$$ \mathcal{GG} $$ GG ), Γ(h→$$ \mathcal{AA} $$ AA ) to incorporate full two loop Standard Model results at the amplitude level, in conjunction with dimension eight SMEFT corrections. We simultaneously report consistent Γ(h→$$ \overline{\Psi}\Psi $$ Ψ ¯ Ψ ) results including leading QCD corrections and dimension eight SMEFT corrections. This extends the predictions of the former processes Γ, σto a full set of corrections at$$ \mathcal{O}\left({\overline{v}}_T^2/{\varLambda}^2{\left(16{\pi}^2\right)}^2\right) $$ O v ¯ T 2 / Λ 2 16 π 2 2 and$$ \mathcal{O}\left({\overline{v}}_T^4/{\Lambda}^4\right) $$ O v ¯ T 4 / Λ 4 , where$$ {\overline{v}}_T $$ v ¯ T is the electroweak scale vacuum expectation value and Λ is the cut off scale of the SMEFT. Throughout, cross consistency between the operator and loop expansions is maintained by the use of the geometric SMEFT formalism. For Γ(h→$$ \overline{\Psi}\Psi $$ Ψ ¯ Ψ ), we include results at$$ \mathcal{O}\left({\overline{v}}_T^2/{\Lambda}^2\left(16{\pi}^2\right)\right) $$ O v ¯ T 2 / Λ 2 16 π 2 in the limit where subleadingmΨ→ 0 corrections are neglected. We clarify how gauge invariant SMEFT renormalization counterterms combine with the Standard Model counter terms in higher order SMEFT calculations when the Background Field Method is used. We also update the prediction of the total Higgs width in the SMEFT to consistently include some of these higher order perturbative effects. 
    more » « less
  5. Abstract We extend the Calderón–Zygmund theory for nonlocal equations tostrongly coupled system of linear nonlocal equations A s u = f {\mathcal{L}^{s}_{A}u=f}, where the operator A s {\mathcal{L}^{s}_{A}}is formally given by A s u = n A ( x , y ) | x - y | n + 2 s ( x - y ) ( x - y ) | x - y | 2 ( u ( x ) - u ( y ) ) 𝑑 y . \mathcal{L}^{s}_{A}u=\int_{\mathbb{R}^{n}}\frac{A(x,y)}{|x-y|^{n+2s}}\frac{(x-%y)\otimes(x-y)}{|x-y|^{2}}(u(x)-u(y))\,dy. For 0 < s < 1 {0<1}and A : n × n {A:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}}taken to be symmetric and serving asa variable coefficient for the operator, the system under consideration is the fractional version of the classical Navier–Lamé linearized elasticity system. The study of the coupled system of nonlocal equations is motivated by its appearance in nonlocal mechanics, primarily in peridynamics. Our regularity result states that if A ( , y ) {A(\,\cdot\,,y)}is uniformly Holder continuous and inf x n A ( x , x ) > 0 {\inf_{x\in\mathbb{R}^{n}}A(x,x)>0}, then for f L loc p {f\in L^{p}_{\rm loc}}, for p 2 {p\geq 2}, the solution vector u H loc 2 s - δ , p {u\in H^{2s-\delta,p}_{\rm loc}}for some δ ( 0 , s ) {\delta\in(0,s)}. 
    more » « less