On Average Distance, Level-1 Fourier Weight, and Chang's Lemma
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |