1 Search Results for "Roy, Sourya"

Document

DOI: 10.4230/LIPIcs.ITCS.2022.20

Mixing of 3-Term Progressions in Quasirandom Groups

Authors: Amey Bhangale, Prahladh Harsha, and Sourya Roy

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

In this paper, we show the mixing of three-term progressions (x, xg, xg²) in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any D-quasirandom group G and any three sets A₁, A₂, A₃ ⊂ G, we have |Pr_{x,y∼ G}[x ∈ A₁, xy ∈ A₂, xy² ∈ A₃] - ∏_{i = 1}³ Pr_{x∼ G}[x ∈ A_i]| ≤ (2/(√{D)})^{1/4}. Prior to this, Tao answered this question when the underlying quasirandom group is SL_{d}(𝔽_q). Subsequently, Peluse extended the result to all non-abelian finite simple groups. In this work, we show that a slight modification of Peluse’s argument is sufficient to fully resolve Gowers' quasirandom conjecture for 3-term progressions. Surprisingly, unlike the proofs of Tao and Peluse, our proof is elementary and only uses basic facts from non-abelian Fourier analysis.

Cite as

Amey Bhangale, Prahladh Harsha, and Sourya Roy. Mixing of 3-Term Progressions in Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 20:1-20:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ITCS.2022.20,
  author =	{Bhangale, Amey and Harsha, Prahladh and Roy, Sourya},
  title =	{{Mixing of 3-Term Progressions in Quasirandom Groups}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{20:1--20:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.20},
  URN =		{urn:nbn:de:0030-drops-156163},
  doi =		{10.4230/LIPIcs.ITCS.2022.20},
  annote =	{Keywords: Quasirandom groups, 3-term arithmetic progressions}
}

Refine by Author
1 Bhangale, Amey
1 Harsha, Prahladh
1 Roy, Sourya

Refine by Classification
1 Mathematics of computing → Combinatoric problems

Refine by Keyword
1 3-term arithmetic progressions
1 Quasirandom groups

Refine by Type
1 document

Refine by Publication Year
1 2022

1 Search Results for "Roy, Sourya"

Mixing of 3-Term Progressions in Quasirandom Groups

Abstract

Cite as

Thanks for your feedback!

Could not send message