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. Universality and phase transitions in low moments of secular coefficients of critical holomorphic multiplicative chaos

   https://doi.org/10.1007/s00440-025-01443-z  

   Gu, Haotian; Zhang, Zhenyuan (November 2025, Probability Theory and Related Fields)

   Abstract We investigate the low moments$$\mathbb {E}[|A_N|^{2q}],\, 0 $E\left[\right|A_N{|}^{2q}],0<q⩽1$of secular coefficients$$A_N$$ $A_N$of the critical non-Gaussian holomorphic multiplicative chaos, i.e. coefficients of$$z^N$$ $z^N$in the power series expansion of$$\exp (\sum _{k=1}^\infty X_kz^k/\sqrt{k})$$ $exp({\sum }_{k=1}^{\infty }{X}_k{z}^k/\sqrt{k})$, where$$\{X_k\}_{k\geqslant 1}$$ ${\left\{X_k\right\}}_{k⩾1}$are i.i.d. rotationally invariant unit variance complex random variables. Inspired by Harper’s remarkable result on random multiplicative functions, Soundararajan and Zaman recently showed that if each$$X_k$$ $X_k$is standard complex Gaussian,$$A_N$$ $A_N$features better-than-square-root cancellation:$$\mathbb {E}[|A_N|^2]=1$$ $E\left[\right|A_N{|}^2]=1$and$$\mathbb {E}[|A_N|^{2q}]\asymp (\log N)^{-q/2}$$ $E\left[\right|A_N{|}^{2q}]\asymp {(logN)}^{-q/2}$for fixed$$q\in (0,1)$$ $q\in (0,1)$as$$N\rightarrow \infty $$ $N\to \infty$. We show that this asymptotics holds universally if$$\mathbb {E}[e^{\gamma |X_k|}]<\infty $$ $E\left[e^{\gamma |X_k|}\right]<\infty$for some$$\gamma >2q$$ $\gamma >2q$. As a consequence, we establish the universality for the tightness of the normalized secular coefficients$$A_N(\log (1+N))^{1/4}$$ $A_N{(log(1+N))}^{1/4}$, generalizing a result of Najnudel, Paquette, and Simm. Another corollary is the almost sure regularity of some critical non-Gaussian holomorphic chaos in appropriate Sobolev spaces. Moreover, we characterize the asymptotics of$$\mathbb {E}[|A_N|^{2q}]$$ $E\left[\right|A_N{|}^{2q}]$for$$|X_k|$$ $|X_k|$following a stretched exponential distribution with an arbitrary scale parameter, which exhibits a completely different behavior and underlying mechanism from the Gaussian universality regime. As a result, we unveil a double-layer phase transition around the critical case of exponential tails. Our proofs combine Harper’s robust approach with a careful analysis of the (possibly random) leading terms in the monomial decomposition of$$A_N$$ $A_N$. 

   more » « less
3. The weight hierarchy of decreasing norm-trace codes

   https://doi.org/10.1007/s10623-025-01619-7  

   Camps-Moreno, Eduardo; López, Hiram H; Matthews, Gretchen L; San-José, Rodrigo (April 2025, Designs, Codes and Cryptography)

   Abstract The Generalized Hamming weights and their relative version, which generalize the minimum distance of a linear code, are relevant to numerous applications, including coding on the wire-tap channel of type II,t-resilient functions, bounding the cardinality of the output in list decoding algorithms, ramp secret sharing schemes, and quantum error correction. The generalized Hamming weights have been determined for some families of codes, including Cartesian codes and Hermitian one-point codes. In this paper, we determine the generalized Hamming weights of decreasing norm-trace codes, which are linear codes defined by evaluating sets of monomials that are closed under divisibility on the rational points of the extended norm-trace curve given by$$x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y$$ $x^u=y^{q^{s-1}}+y^{q^{s-2}}+\cdots +y$over the finite field of cardinality$$q^s$$ $q^s$, whereuis a positive divisor of$$\frac{q^s - 1}{q - 1}$$ $\frac{q^s-1}{q-1}$. As a particular case, we obtain the weight hierarchy of one-point norm-trace codes and recover the result of Barbero and Munuera (2001) giving the weight hierarchy of one-point Hermitian codes. We also study the relative generalized Hamming weights for these codes and use them to construct impure quantum codes with excellent parameters. 

   more » « less
4. A case study of SMEFT $$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ effects in diboson processes: pp → W±(ℓ±ν)γ

   https://doi.org/10.1007/JHEP05(2024)223  

   Martin, Adam (May 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> In this paper we explorepp→W^±(ℓ^±ν)γto$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ $O\left(1/{\Lambda }^4\right)$in the SMEFT expansion. Calculations to this order are necessary to properly capture SMEFT contributions that grow with energy, as the interference between energy-enhanced SMEFT effects at$$ \mathcal{O}\left(1/{\Lambda}^2\right) $$ $O\left(1/{\Lambda }^2\right)$and the Standard Model is suppressed. We find that there are several dimension eight operators that interfere with the Standard Model and lead to the same energy growth, ~$$ \mathcal{O}\left({E}^4/{\Lambda}^4\right) $$ $O\left(E^4/{\Lambda }^4\right)$, as dimension six squared. While energy-enhanced SMEFT contributions are a main focus, our calculation includes the complete set of$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ $O\left(1/{\Lambda }^4\right)$SMEFT effects consistent with U(3)⁵flavor symmetry. Additionally, we include the decay of theW^±→ ℓ^±ν, making the calculation actually$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$ $\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$. As such, we are able to study the impact of non-resonant SMEFT operators, such as$$ \left({L}^{\dagger }{\overline{\sigma}}^{\mu }{\tau}^IL\right)\left({Q}^{\dagger }{\overline{\sigma}}^{\nu }{\tau}^IQ\right) $$ $\left(L^{†}{\overline{\sigma }}^{\mu }{\tau }^{I}L\right)\left(Q^{†}{\overline{\sigma }}^{\nu }{\tau }^{I}Q\right)$B_μν, which contribute to$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$ $\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$directly and not to$$ \overline{q}{q}^{\prime}\to {W}^{\pm}\gamma $$ $\overline{q}{q}^{\prime }\to W^{\pm }\gamma$. We show several distributions to illustrate the shape differences of the different contributions. 

   more » « less
5. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil; Williams, R_Ryan (November 2022, Theory of Computing Systems)

   Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$ $\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$$\mathcal { C}$$ $C$, by showing that$$\mathcal { C}$$ $C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class$${\mathcal C}$$ $C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of$${\sum }_{i} x_{i}$$ ${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$$\mathcal { C}$$ $C$, faster#SAT algorithms for$$\mathcal { C}$$ $C$circuits imply lower bounds against the circuit class$$f \circ \mathcal { C}$$ $f\circ C$, which may bestrongerthan$$\mathcal { C}$$ $C$itself. In particular:#SAT algorithms forn^k-size$$\mathcal { C}$$ $C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$$(f \circ \mathcal { C})$$ $(f\circ C)$-circuits of polynomial size.#SAT algorithms for$$2^{n^{{\varepsilon }}}$$ $2^{n^{\epsilon }}$-size$$\mathcal { C}$$ $C$-circuits running in$$2^{n-n^{{\varepsilon }}}$$ $2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$$(f \circ \mathcal { C})$$ $(f\circ C)$-circuits of polynomial size. Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class. 

   more » « less