Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2504.02593 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915225811288064 |
|---|---|
| author | Yu, Lei |
| author_facet | Yu, Lei |
| contents | In this paper, we improve the well-known level-1 weight bound, also known as Chang's lemma, by using an induction method. Our bounds are close to optimal no matter when the set is large or small. Our bounds can be seen as bounds on the minimum average distance problem, since maximizing the level-1 weight is equivalent to minimizing the average distance. We apply our new bounds to improve the Friedgut--Kalai--Naor theorem. We also derive the sharp version for Chang's original lemma for $\mathbb{F}_{2}^{n}$. That is, we show that in $\mathbb{F}_{2}^{n}$, Hamming balls maximize the dimension of the space spanned by large Fourier coefficients. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02593 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Average Distance, Level-1 Fourier Weight, and Chang's Lemma Yu, Lei Combinatorics Discrete Mathematics Information Theory In this paper, we improve the well-known level-1 weight bound, also known as Chang's lemma, by using an induction method. Our bounds are close to optimal no matter when the set is large or small. Our bounds can be seen as bounds on the minimum average distance problem, since maximizing the level-1 weight is equivalent to minimizing the average distance. We apply our new bounds to improve the Friedgut--Kalai--Naor theorem. We also derive the sharp version for Chang's original lemma for $\mathbb{F}_{2}^{n}$. That is, we show that in $\mathbb{F}_{2}^{n}$, Hamming balls maximize the dimension of the space spanned by large Fourier coefficients. |
| title | On Average Distance, Level-1 Fourier Weight, and Chang's Lemma |
| topic | Combinatorics Discrete Mathematics Information Theory |
| url | https://arxiv.org/abs/2504.02593 |