Timeline for Largest Fourier coefficient of sparse boolean function
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2015 at 18:42 | comment | added | David Harris | @ მამუკა ჯიბლაძე -- you are absolutely right, I fixed this in the question. | |
| May 2, 2015 at 20:21 | comment | added | David Harris | @Ben, Can you please expand on this, and either provide a citation or make it an answer? Thanks a lot | |
| May 2, 2015 at 20:20 | history | edited | David Harris | CC BY-SA 3.0 |
deleted 9 characters in body
|
| May 2, 2015 at 18:40 | comment | added | Ben Green | Tom got back to me. You can indeed get such a bound by considering the (2k)th moment of f^(gamma), for which you can find a lower bound by expanding out combinatorially and using the Cauchy-Schwarz inequality to bound the number of solutions to x_1 + ... + x_k = y_1 + ... + y_k with f(x_i), f(y_j) = 1. Then ignore the term gamma = 0 and optimise by taking k ~ n/c. | |
| May 2, 2015 at 17:49 | comment | added | Ben Green | I think Tom Sanders considered this question and may have had an argument to show that F(n,cn) > c' 2^n, where c' depends only on c, but I don't remember exactly. I'll ask him. I think this is closely related to the issue of getting a bound on the Sidon constant s(X \cup Y) in terms of s(X) and s(Y) (known, due to work of Rider in the 1970s), together with the fact that a dissociated subset of GF(2)^n is Sidon, where Sidon is in the harmonic analysis sense webpages.uidaho.edu/lnguyen/SidonSet_RieszProduct.pdf. | |
| May 2, 2015 at 17:22 | comment | added | მამუკა ჯიბლაძე | Then I don't quite understand - is not always $|\hat f(\gamma)|\le\sum f(i)$? I mean, $\hat f(\gamma)$ is placed between numbers obtained when either each $(-1)^{i\cdot\gamma}$ is $1$, or each of them is $-1$, i. e. between $\pm\sum f(i)$ | |
| May 2, 2015 at 15:48 | history | edited | David Harris | CC BY-SA 3.0 |
added 229 characters in body
|
| May 2, 2015 at 15:47 | comment | added | David Harris | Yes, $\gamma \in GF(2)^n$, and this is the standard dot-product. | |
| May 2, 2015 at 15:20 | history | edited | Yemon Choi | CC BY-SA 3.0 |
added CO tag
|
| May 2, 2015 at 15:19 | comment | added | მამუკა ჯიბლაძე | So $\gamma$ is again in $GF(2)^n$ and $.$ is the standard scalar product? | |
| May 2, 2015 at 15:08 | history | asked | David Harris | CC BY-SA 3.0 |