More Like this

1. On approximability of satisfiable $$\boldsymbol {k}$$-CSPs: II

   https://doi.org/10.1017/S0963548325100114  

   Bhangale, Amey; Khot, Subhash; Minzer, Dor (November 2025, Combinatorics, Probability and Computing)

   Abstract Let$$\Sigma$$be an alphabet and$$\mu$$be a distribution on$$\Sigma ^k$$for some$$k \geqslant 2$$. Let$$\alpha \gt 0$$be the minimum probability of a tuple in the support of$$\mu$$(denoted$$\mathsf{supp}(\mu )$$). We treat the parameters$$\Sigma , k, \mu , \alpha$$as fixed and constant. We say that the distribution$$\mu$$has a linear embedding if there exist an Abelian group$$G$$(with the identity element$$0_G$$) and mappings$$\sigma _i : \Sigma \rightarrow G$$,$$1 \leqslant i \leqslant k$$, such that at least one of the mappings is non-constant and for every$$(a_1, a_2, \ldots , a_k)\in \mathsf{supp}(\mu )$$,$$\sum _{i=1}^k \sigma _i(a_i) = 0_G$$. In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let$$f_i: \Sigma ^n\rightarrow [\!-1,1]$$be bounded functions, such that at least one of the functions$$f_i$$essentially has degree at least$$d$$, meaning that the Fourier mass of$$f_i$$on terms of degree less than$$d$$is at most$$\delta$$. If$$\mu$$has no linear embedding (over any Abelian group), then is it necessarily the case that\begin{equation*}\left | \mathop {\mathbb{E}}_{({\textbf {x}}_1, {\textbf {x}}_2, \ldots , {\textbf {x}}_k)\sim \mu ^{\otimes n}}[f_1({\textbf {x}}_1)f_2({\textbf {x}}_2)\cdots f_k({\textbf {x}}_k)] \right | = o_{d, \delta }(1),\end{equation*}where the right hand side$$\to 0$$as the degree$$d \to \infty$$and$$\delta \to 0$$? In this paper, we answer this analytical question fully and in the affirmative for$$k=3$$. We also show the following two applications of the result.1.The first application is related to hardness of approximation. Using the reduction from [5], we show that for every$$3$$-ary predicate$$P:\Sigma ^3 \to \{0,1\}$$such that$$P$$has no linear embedding, anSDP (semi-definite programming) integrality gap instanceof a$$P$$-Constraint Satisfaction Problem (CSP) instance with gap$$(1,s)$$can be translated into a dictatorship test with completeness$$1$$and soundness$$s+o(1)$$, under certain additional conditions on the instance.2.The second application is related to additive combinatorics. We show that if the distribution$$\mu$$on$$\Sigma ^3$$has no linear embedding, marginals of$$\mu$$are uniform on$$\Sigma$$, and$$(a,a,a)\in \texttt{supp}(\mu )$$for every$$a\in \Sigma$$, then every large enough subset of$$\Sigma ^n$$contains a triple$$({\textbf {x}}_1, {\textbf {x}}_2,{\textbf {x}}_3)$$from$$\mu ^{\otimes n}$$(and in fact a significant density of such triples). 

   more » « less
2. Generic Beauville’s Conjecture

   https://doi.org/10.1017/fms.2024.21  

   Coskun, Izzet; Larson, Eric; Vogt, Isabel (January 2024, Forum of Mathematics, Sigma)

   Abstract Let$$\alpha \colon X \to Y$$be a finite cover of smooth curves. Beauville conjectured that the pushforward of a general vector bundle under$$\alpha $$is semistable if the genus ofYis at least$$1$$and stable if the genus ofYis at least$$2$$. We prove this conjecture if the map$$\alpha $$is general in any component of the Hurwitz space of covers of an arbitrary smooth curveY. 

   more » « less
3. Multi-linear forms, graphs, and $L^p$-improving measures in $${\Bbb F}_q^d$$

   https://doi.org/10.4153/S0008414X2300086X  

   Bhowmik, Pablo; Iosevich, Alex; Koh, Doowon; Pham, Thang (February 2025, Canadian journal of mathematics)

   Abstract The purpose of this paper is to introduce and study the following graph-theoretic paradigm. Let$$ \begin{align*}T_Kf(x)=\int K(x,y) f(y) d\mu(y),\end{align*} $$where$$f: X \to {\Bbb R}$$,Xa set, finite or infinite, andKand$$\mu $$denote a suitable kernel and a measure, respectively. Given a connected ordered graphGonnvertices, consider the multi-linear form$$ \begin{align*}\Lambda_G(f_1,f_2, \dots, f_n)=\int_{x^1, \dots, x^n \in X} \ \prod_{(i,j) \in {\mathcal E}(G)} K(x^i,x^j) \prod_{l=1}^n f_l(x^l) d\mu(x^l),\end{align*} $$where$${\mathcal E}(G)$$is the edge set ofG. Define$$\Lambda _G(p_1, \ldots , p_n)$$as the smallest constant$$C>0$$such that the inequality(0.1)$$ \begin{align} \Lambda_G(f_1, \dots, f_n) \leq C \prod_{i=1}^n {||f_i||}_{L^{p_i}(X, \mu)} \end{align} $$holds for all nonnegative real-valued functions$$f_i$$,$$1\le i\le n$$, onX. The basic question is, how does the structure ofGand the mapping properties of the operator$$T_K$$influence the sharp exponents in (0.1). In this paper, this question is investigated mainly in the case$$X={\Bbb F}_q^d$$, thed-dimensional vector space over the field withqelements,$$K(x^i,x^j)$$is the indicator function of the sphere evaluated at$$x^i-x^j$$, and connected graphsGwith at most four vertices. 

   more » « less
4. On cohesive powers of linear orders

   https://doi.org/10.1017/jsl.2023.14  

   Dimitrov, Rumen; Harizanov, Valentina; Morozov, Andrey; Shafer, Paul; Soskova, Alexandra A; Vatev, Stefan V (September 2023, The Journal of Symbolic Logic)

   Abstract Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$$\omega $$,$$\zeta $$, and$$\eta $$denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$$\omega $$. If$$\mathcal {L}$$is a computable copy of$$\omega $$that is computably isomorphic to the usual presentation of$$\omega $$, then every cohesive power of$$\mathcal {L}$$has order-type$$\omega + \zeta \eta $$. However, there are computable copies of$$\omega $$, necessarily not computably isomorphic to the usual presentation, having cohesive powers not elementarily equivalent to$$\omega + \zeta \eta $$. For example, we show that there is a computable copy of$$\omega $$with a cohesive power of order-type$$\omega + \eta $$. Our most general result is that if$$X \subseteq \mathbb {N} \setminus \{0\}$$is a Boolean combination of$$\Sigma _2$$sets, thought of as a set of finite order-types, then there is a computable copy of$$\omega $$with a cohesive power of order-type$$\omega + \boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$$, where$$\boldsymbol {\sigma }(X \cup \{\omega + \zeta \eta + \omega ^*\})$$denotes the shuffle of the order-types inXand the order-type$$\omega + \zeta \eta + \omega ^*$$. Furthermore, ifXis finite and non-empty, then there is a computable copy of$$\omega $$with a cohesive power of order-type$$\omega + \boldsymbol {\sigma }(X)$$. 

   more » « less
5. Polynomial progressions in topological fields

   https://doi.org/10.1017/fms.2024.104  

   Krause, Ben; Mirek, Mariusz; Peluse, Sarah; Wright, James (January 2024, Forum of Mathematics, Sigma)

   Abstract Let$$P_1, \ldots , P_m \in \mathbb {K}[\mathrm {y}]$$be polynomials with distinct degrees, no constant terms and coefficients in a general local field$$\mathbb {K}$$. We give a quantitative count of the number of polynomial progressions$$x, x+P_1(y), \ldots , x + P_m(y)$$lying in a set$$S\subseteq \mathbb {K}$$of positive density. The proof relies on a general$$L^{\infty }$$inverse theorem which is of independent interest. This inverse theorem implies a Sobolev improving estimate for multilinear polynomial averaging operators which in turn implies our quantitative estimate for polynomial progressions. This general Sobolev inequality has the potential to be applied in a number of problems in real, complex andp-adic analysis. 

   more » « less