Timeline for Can we explicitly compute this "shift"-quantity over Boolean functions $u:\mathbb{F}_2^n\rightarrow \mathbb{F}_2$?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2022 at 18:43 | comment | added | მამუკა ჯიბლაძე | Experimentally, $A(1)=4$, $A(3)=64$, $A(5)=640$, $A(7)=17920$ | |
| Aug 5, 2022 at 18:31 | comment | added | მამუკა ჯიბლაძე | Is not $f(n)^2<2^n-1$ for all $n>1$? | |
| Aug 5, 2022 at 18:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 7, 2022 at 17:03 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 9, 2022 at 11:48 | comment | added | Asaf Shachar | @mathworker21 That is a good question. And indeed should be easy to program and check for small values of $n$...(If my programming skills were not so close to nonexistent). | |
| Mar 8, 2022 at 16:50 | answer | added | kodlu | timeline score: 1 | |
| Mar 7, 2022 at 15:47 | comment | added | Joseph Van Name | If $A,B$ are abelian groups and $f:A\rightarrow B$ is a function, then define $$NB_{f}=\sum_{a\in A,a\neq 0}\sum_{b\in B}(f^{-1}[\{b\}]-\frac{|A|}{|B|})^{2}.$$ The quantity $NB_{f}$ as studied in the 2007 paper Nonlinearities of S-boxes by Claude Carlet and Cunsheng Ding, and $$NB_{u}=\frac{1}{2}\sum_{a\in\mathbb{F}_{2}^{n},a\neq 0}\sum_{x\in \mathbb{F}_{2}^{n}}(-1)^{u(x)+u(x+a)}.$$ | |
| Mar 7, 2022 at 15:04 | comment | added | Ofir Gorodetsky | Restatement: Discrete Fourier analysis on $\mathbb{F}_2^n$ allows us to write $(-1)^{u(x)} = \sum_{v \in \mathbb{F}_2^n} a_v (-1)^{\langle v,x \rangle}$ where $a_v$ is the Fourier transform of $(-1)^{u(x)}$. Orthogonality of $x \mapsto (-1)^{\langle v,x\rangle}$ allows us to eventually write your sum $\sum_{a \neq 0}(\cdots)^2$ as $2^{3n} \left( \sum_{v \in \mathbb{F}_2^n} a_v^4 - 2^n\right)$, so you want to minimize the Fourth moment of the Fourier transform of a function assuming the values $\pm 1$. By Plancheral, $\sum_{v} a_v^2 = 2^n$, and by C-S, $\sum_{v} a_v^4 \ge 2^n$. | |
| Mar 7, 2022 at 13:49 | comment | added | mathworker21 | what's answer for $n=1,3,5$? | |
| Mar 7, 2022 at 13:37 | history | edited | Asaf Shachar | CC BY-SA 4.0 |
added 12 characters in body
|
| Mar 7, 2022 at 13:31 | history | asked | Asaf Shachar | CC BY-SA 4.0 |