More Like this

1. On correlation bounds against polynomials Leibniz International Proceedings in Informatics (LIPIcs):38th Computational Complexity Conference (CCC 2023)

   https://doi.org/10.4230/LIPIcs.CCC.2023.3  

   Ivanov, Peter ; Pavlovic, Liam ; Viola, Emanuele ( January 2023 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ta-Shma, Amnon (Ed.)

   We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over 𝔽₂. Our main contributions include: 1) In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their technique generalizes to higher degree polynomials as well. We give a counterexample to their conjecture, in fact ruling out weaker parameters and showing what they prove is essentially the best possible. 2) We propose a new approach for proving correlation bounds with the central "mod functions," consisting of two steps: (I) the polynomials that maximize correlation are symmetric and (II) symmetric polynomials have small correlation. Contrary to related results in the literature, we conjecture that (I) is true. We argue this approach is not affected by existing "barrier results." 3) We prove our conjecture for quadratic polynomials. Specifically, we determine the maximum possible correlation between quadratic polynomials modulo 2 and the functions (x_1,… ,x_n) → z^{∑ x_i} for any z on the complex unit circle, and show that it is achieved by symmetric polynomials. To obtain our results we develop a new proof technique: we express correlation in terms of directional derivatives and analyze it by slowly restricting the direction. 4) We make partial progress on the conjecture for cubic polynomials, in particular proving tight correlation bounds for cubic polynomials whose degree-3 part is symmetric. 

   more » « less
2. Counterexamples to the tilting and (p,r)-filtration conjectures

   https://doi.org/10.1515/crelle-2019-0036  

   Bendel, Christopher P. ; Nakano, Daniel K. ; Pillen, Cornelius ; Sobaje, Paul ( November 2019 , Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract In this paper the authors produce a projective indecomposable module for the Frobenius kernel of a simple algebraic group in characteristic p that is not the restriction of an indecomposable tilting module. This yields a counterexample to Donkin’s longstanding Tilting Module Conjecture. The authors also produce a Weyl module that does not admit a p -Weyl filtration. This answers an old question of Jantzen, and also provides a counterexample to the {(p,r)} -Filtration Conjecture. 

   more » « less
3. Degrees of symmetric Grothendieck polynomials and Castelnuovo-Mumford regularity

   https://doi.org/10.1090/proc/15294  

   Rajchgot, Jenna ; Ren, Yi ; Robichaux, Colleen ; Dizier, Avery St ; Weigandt, Anna ( April 2021 , Proceedings of the American Mathematical Society)

   We give an explicit formula for the degree of the Grothendieck polynomial of a Grassmannian permutation and a closely related formula for the Castelnuovo-Mumford regularity of the Schubert determinantal ideal of a Grassmannian permutation. We then provide a counterexample to a conjecture of Kummini-Lakshmibai-Sastry-Seshadri on a formula for regularities of standard open patches of particular Grassmannian Schubert varieties and show that our work gives rise to an alternate explicit formula in these cases. We end with a new conjecture on the regularities of standard open patches ofarbitraryGrassmannian Schubert varieties. 

   more » « less
4. A counterexample to the HK-conjecture that is principal

   https://doi.org/10.1017/etds.2022.25  

   DEELEY, ROBIN J. ( June 2023 , Ergodic Theory and Dynamical Systems)

   Abstract Scarparo has constructed counterexamples to Matui’s HK-conjecture. These counterexamples and other known counterexamples are essentially principal but not principal. In the present paper, a counterexample to the HK-conjecture that is principal is given. Like Scarparo’s original counterexample, our counterexample is the transformation groupoid associated to a particular odometer. However, the relevant group is the fundamental group of a flat manifold (and hence is torsion-free) and the associated odometer action is free. The examples discussed here do satisfy the rational version of the HK-conjecture. 

   more » « less
5. A counterexample to the periodic tiling conjecture

   Greenfeld, Rachel ; Tao, Terence ( July 2024 , Annals of mathematics)

   The periodic tiling conjecture asserts that any finite subset of a lattice $\mathbb{Z}^d$ that tiles that lattice by translations, in fact tiles periodically. In this work we disprove this conjecture for sufficiently large $d$, which also implies a disproof of the corresponding conjecture for Euclidean spaces $\mathbb{R}^d$. In fact, we also obtain a counterexample in a group of the form $\mathbb{Z}^2 \times G_0$ for some finite abelian $2$-group $G_0$. Our methods rely on encoding a "Sudoku puzzle'' whose rows and other non-horizontal lines are constrained to lie in a certain class of "$2$-adically structured functions'', in terms of certain functional equations that can be encoded in turn as a single tiling equation, and then demonstrating that solutions to this Sudoku puzzle exist, but are all non-periodic. 

   more » « less