Dependencies

If \(a\) is \(\varepsilon \)-close to \(n\) entropy, then for any PMF \(b\), \(a+b\) is also \(\varepsilon \)-close to \(n\) entropy.

If \(A \cap C \neq \emptyset \), we have \(|B+C| \leq \frac{|B+A| |C+C|}{|A \cap C|}\).

For any set \(A\) and two values \(a, b\), we have \((a+b)A \subseteq aA + bA\).

For a character \(\chi \), \(\chi (a) = \chi (b)\) iff \(\chi (a-b) = 1\).

We have that \(Q(A, x A)\) for \(x \neq 0\) is the number of quadruples \((a, b, c, d) \in A^4\) such that \(a + x b = c + x d\).

For any linear equivalence, applying it to lines is injective.

The function in the previous lemma is actually a bijection.

If \(\chi \) is a non-trivial character of a field \(\mathbb {F}\), then there is an injective function from elements of \(\mathbb {F}^2\) (red generalize this to any dimension) to characters of it, defined by \(f(x)(y) = \chi (x \cdot y)\).

We have \(\lVert \sigma \# U - U \rVert _{\ell ^1} \leq \frac nm\).

\(C_b = \sqrt[64]{16C + 1}\).

For any two sources \(a, b\) with maximum value at most \(p^{-1/2 + 2/11 \alpha }\), and any non-trivial character \(\chi \),

Note: the inner product and DFT here aren’t normalized.

where \(P\) reorders \(\hat b\) based on 12.4

For any bilinear form \(F\) and character \(\chi \),

For any bilinear form \(F\) and character \(\chi \),

If \(a\) and \(b\) are \(\varepsilon \)-close to \(N\) entropy, then

For any source \(a\) with maximum value at most \(p^{-1/2 + 2/11 \alpha }\), \(D \# L(a, M \# (a \times a))\) is \(8 C p^{-2/11 \alpha }\)-close to \(p^{1+2/11 \alpha }\) entropy.

For any positive integer \(m\), the function \(f(x, y) = (xy + x^2 y^2 \bmod p) \bmod {m}\) is a two source extractor, with \(k = (1/2 - 2/11 \alpha ) \log (p), \varepsilon = C_b p^{-1/352 \alpha } \sqrt{m} (3 \ln (p) + 3) + \frac{m}{2p}\).

For any positive integer \(m\) and two sources \(a, b\) with maximum value at most \(p^{-1/2 + 2/11 \alpha }\), the statistical distance of \(f \# (a \times b)\) with \(f(x, y) = (xy + x^2 y^2 \bmod p) \bmod {m}\) to the uniform distribution is at most \(\varepsilon = C_b p^{-1/352 \alpha } \sqrt{m} (3 \ln (p) + 3) + \frac{m}{2p}\).

\(\alpha = \operatorname{\varepsilon }(\beta )\)

\(\beta = \frac{35686629198734976}{35686629198734977}\).

\(\alpha = \frac{11}2(1 - \beta )\).

For any set \(A\) and a non-zero value \(x\), we have \(|xA| = |A|\)

For a real \(x\), we have \(2 - |4x - 2| \leq |e^{x 2\pi i} - 1|\).

Let \(S_1, S_2, \dots , S_k \subseteq S\) be finite sets with \(|S_i| \geq \delta |S|\) for all \(i\). Then, there exists \(i\) such that \(|\{ j | |S_j \cap S_i| \geq (\delta ^2 / 2) k\} | \geq (\delta ^2 / 2) k\)

We say that a distribution \(a\) is \(\varepsilon \)-close to \(N\) entropy if for all sets \(|A| \leq N\), \(\sum _{x \in A} a(x) \leq \varepsilon \). Note that this is a bit different than the usual definition.

If \(e\) is an isomorphism and \(a\) is \(\varepsilon \)-close to \(n\) entropy, \(e \# a\) is also \(\varepsilon \)-close to \(n\) entropy.

If, for all \(x\) such that \(0 {\lt} f(x)\), we have that \(g(x)\) is \(\varepsilon \)-close to \(n\) entropy, then \(g(f)\) is \(\varepsilon \)-close to \(n\) entropy.

If \(a\) is \(\varepsilon \)-close to \(\lfloor n \rfloor \) entropy it’s also \(\varepsilon \)-close to \(n\) entropy.

If \(a\) is \(\varepsilon _1\)-close to \(n\) entropy and \(\varepsilon _1 \leq \varepsilon _2\) it’s also \(\varepsilon _2\)-close to \(n\) entropy.

If \(h\) is an additive homomorphism we have \(h \circ (f \# g) = f \# (g \circ h)\).

Given a set \(P\) of points and a set \(L\) of lines, the number of incidences is at most \(\sqrt{|L| |P| (|P| + |L|)}\).

\(D(x,y) = (x, x^2 - y)\).

If \(f\) is a bijection we have \((f \# g)(x) = g (f^{-1}(x))\).

For any set \(A\) over a finite field of size \(q\) there is a value \(a \neq 0\) such that \(|A + a A| \geq \frac{\min (|A|^2, q)}2\).

For any probability distribution \(a\), there are at most \(n\) values such that \(a(x) {\gt} 1/n\).

A finite probability distribution is a function \(f : A \to \mathbb {R}\) from a finite type \(A\), such that \(f\) is nonnegative and the sum of \(f\) is 1.

Given a finite probability distribution \(f: A \to \mathbb {R}\) and a function \(g : A \to B\), we can apply \(g\) to the random variable represented by \(f\). This gives the distribution \(g \# f\).

We have \((f \# a) + (g \# b) = h \# (a \times b)\), with \(h(x, y) = f(x) + g(y)\).

We have \((f \# a) \times (g \# b) = h \# (a \times b)\), with \(h(x, y) = (f(x), g(y))\).

We have \(f \# (a \times b) = b \times a\) for \(f(x, y) = (y, x)\).

Given a finite probability distribution \(f: A \to \mathbb {R}\) and a list of finite probability distributions on \(B\), indexed by elements of \(A\), \(g\), we can define \(g(f)\) as the probability distribution obtained by sampling an element from \(f\), and then sampling an elemente from the corresponding distribution in \(g\).

These operations define a commutative monoid.

Let \(X\) be a distribution \(\mathbb {Z}_N\) such that for every nontrivial character \(\chi \), \(\hat{X}(\chi ) \leq \frac{\varepsilon }{|G|}\). Then \(\operatorname{\operatorname {SD}}(\sigma \# X, U) \leq \varepsilon \sqrt{M} (3\ln (N) + 3) + \frac{M}{2N}\).

For any set \(A\) in \(\mathbb {F}_p\) (for \(p\) prime), we have \(|3 A^2 - 3 A^2| \geq \frac{\min (|A|^2, p)}2\).

Given two finite probability distributions \(f: A \to \mathbb {R}, g : A \to \mathbb {R}\), we have a probability distribution defines as \(f+g = a \# (f \times g)\) with \(a(x, y) = x+y\).

Given two finite probability distributions \(f: A \to \mathbb {R}, g : B \to \mathbb {R}\), we have a probability distribution from \(A \times B\) defines as \((f \times g)(x, y) = f(x) g(y)\).

Given a finite probability distribution \(f: A \to \mathbb {R}\), we have a probability distribution defines as \(-f = n \# f\) with \(n(x) = -x\).

Given two finite probability distributions \(f: A \to \mathbb {R}, g : A \to \mathbb {R}\), we have a probability distribution defines as \(f-g = s \# (f \times g)\) with \(s(x, y) = x-y\).

The inner product is commutitive.

\(f \# (b \times b \times b) = D \# L(b, M \# (b \times b))\), with \(f(x, y, z) = (x+y+z, x^2+y^2+z^2)\).

For a function \(f\) with domain \(A\),

For a function \(f\) with domain \(A\)

Note that in this lemma \(\langle f, g \rangle \) is \(\sum _x \bar{f(x)} {g(x)}\).

Given a distribution \(A\) on \(\mathbb {F}\), and a distribution \(B\) on \(\mathbb {F}^3\), we define a distribution \(L(A, B)\) by sampling \(x\) from \(A\), sampling \((y, z, w)\) from \(B\), and outputting \((x + y, z(x + y) + w)\).

We have \(L(f(A), g(B)) = L'(A\times B)\) with \(L'(x, y) = L(f(x), g(y))\).

If \(a, b, n\) are reals, \(b, n\) are positive, and \(\frac ab \leq n\), then \(\frac ab \leq \frac{a+1}{b + 1/n}\).

This is a very slight generalization of Lemma 4.3 in [Rao07]:

Let \(G, H\) be finite abelian groups. Let \(X\) be a function \(G \to \mathbb {R}\) such that for every nontrivial character \(\chi \), \(\hat{X}(\chi ) \leq \frac{\varepsilon }{|G|}\) and let \(U\) be the function with constant value \(E_x[X(x)]\). Let \(\sigma : G \to H\) be a function such that for every character \(\phi \), we have \(\lVert \widehat{\phi \circ \sigma } \rVert _{\ell ^1} \leq \tau \). Then \(\lVert \sigma \# X - \sigma \# U \rVert _{\ell ^1} \leq \tau \varepsilon \sqrt{|H|}\)

This is Lemma 4.4 in [Rao07] with explicit constants:

For any character \(\chi \) of \(\mathbb {Z}_M\), \(\lVert \widehat{\chi \circ \sigma }\rVert _{\ell ^1} \leq 6 \ln (N) + 6\)

A line over a field \(\mathbb {F}\) is a linear subspace of \(\mathbb {F}^3\) of dimension 2.

Given a linear isomorphism \(P\) and a line \(L\), we have a line \(PL\).

A point \((x, y) \in \mathbb {F}^2\) is in a line \(L\) iff \((x, y, 1) \in L\).

TODO

Given an integer \(N\) and a real number \(\beta \) such that \(p^\beta \leq N \leq p^{2 - \beta }\), and two nonempty sets \(A' \subseteq \mathbb {F}, B'\subseteq \mathbb {F}^3\), such that \(|B'| \leq N\) and the last two values in every element of \(B'\) are unique, then \(L(\operatorname{\operatorname {Uniform}}(A'), \operatorname{\operatorname {Uniform}}(B'))\) is \(\frac{C}{|A'| |B'|} N^{3/2 - \operatorname{\varepsilon }(\beta )}\)-close to \(N\) entropy.

TODO

We have \(g \# f(a) = h(a)\) with \(h(x) = g\# f(x)\).

We have \(f(g(a)) = h(a)\) with \(h(x) = g(f(x))\).

\(M(x, y) = (x+y, 2(x+y), -((x+y)^2 + x^2 + y^2))\)

For a function \(f\) with domain \(A\)

If the maximum value of \(a\) is \(\varepsilon \), the maximum value of \(M \# (a \times a)\) is at most \(2 \varepsilon ^2\).

we have \(-(A \cap B) = -A \cap -B\)

Given a point \(p\) not on the line between \((x_1, y_1), (x_2, y_2)\), the projective transformation defined by those points doesn’t move it to infinity.

If \(A \neq \emptyset \) and \(a \in \operatorname{\operatorname {Stab}}_K(A)\) then \(1 \leq K\).

Given two different values, \((x_1, y_1), (x_2, y_2) \in \mathbb {F}^2, (x_1, y_1) \neq (x_2, y_2)\), we get a linear isomorphism \(A\) such that \(A (x_1, y_1, 1) = (1, 0, 0)\) and \(A (x_2, y_2, 1) = (0, 1, 0)\).

\(C = C_2 + 1\)

\(C_2 = \sqrt{2(C_3 + \frac{\sqrt2}4)}\)

Let there be two sets \(A, B\) and a set \(L\) of lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Then the number of intersections is at most \(C' n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).

Let there be two sets \(A, B\) and a set \(L\) of lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Additionally, suppose there are at least \(n^{\frac12 - \operatorname{\varepsilon '}(\beta )}\) points on each line. Then the number of intersections is at most \(C'_2 n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).

Let there be two sets \(A, B\) and a set \(L\) of non-horizontal lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Additionally, suppose there are at least \(n^{\frac12 - \operatorname{\varepsilon '}(\beta )}\) points on each line. Then the number of intersections is at most \(C'_2 n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).

Let there be two sets \(A, B\) and a set \(L\) of non-horizontal lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Suppose there are at least \(n^{\frac12 - \operatorname{\varepsilon '}(\beta )}\) points on each line, and lastly, suppose there are two values \(b_1, b_2 \notin B\), TODO. Then \(|B|\) is at most \(C'_5 n^{1/2 - \operatorname{\varepsilon '_2}(\beta ) - \operatorname{\varepsilon '}(\beta ) - 4 \operatorname{\varepsilon }(\beta )}\).

Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Then the number of intersections is at most \( C n^{\frac32 - \operatorname{\varepsilon }(\beta )} \).

Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\), and each point contained in at least \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines and at most \(4 n^{\frac12 + \operatorname{\varepsilon }(\beta )}\). Then the number of intersections is at most \(C_3 n^{\frac32 - \operatorname{\varepsilon _2}(\beta )}\).

Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\), and each point intersecting with at least \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines. Then the number of intersections is at most \(C_2 n^{\frac32 - \operatorname{\varepsilon }(\beta )}\).

\(\operatorname{\varepsilon }(\beta ) = \operatorname{\varepsilon _2}(\beta ) / 3\)

Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\), two different points \(p_1, p_2\), which are both contained in at most \(4 n^{\frac12 + \operatorname{\varepsilon }(\beta )}\) lines, with no points in \(P\) on the line \(p_1 p_2\), and all points in \(P\) on an intersection of some line from \(p_1\) and some line from \(p_2\). Then the number of intersections is at most \(C' n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).

\(\operatorname{\operatorname {Stab}}_K(A)\) is the set \(\{ x | |A + x A| \leq K |A|\} \).

We have \(\operatorname{\operatorname {Stab}}_{K_1}(A) + \operatorname{\operatorname {Stab}}_{K_2}(A) \subseteq \operatorname{\operatorname {Stab}}_{K_1^8 K_2}(A)\).

For \(a \in \operatorname{\operatorname {Stab}}_{K_1}(A), b \in \operatorname{\operatorname {Stab}}_{K_2}(A)\), we have \(a+b \in \operatorname{\operatorname {Stab}}_{K_1^8 K_2}(A)\).

We have \(\frac{\min (|\operatorname{\operatorname {Stab}}_K(A)|^2, p)}2 \leq |\operatorname{\operatorname {Stab}}_{K^{374}}(A)|\).

If \(4 \leq |\operatorname{\operatorname {Stab}}_K(A)|\) for all \(n \in \mathbb {N}\), \(\min (|\operatorname{\operatorname {Stab}}_K(A)|^{\left(\frac32\right)^n}, \frac p2) \leq |\operatorname{\operatorname {Stab}}_{K^{374^n}}(A)|\).

If \(4 \leq |\operatorname{\operatorname {Stab}}_K(A)|\), then \(\min (|\operatorname{\operatorname {Stab}}_K(A)|^{\frac32}, \frac p2) \leq |\operatorname{\operatorname {Stab}}_{K^{374}}(A)|\).

If \(4 \leq |\operatorname{\operatorname {Stab}}_K(A)|\) and \(p^\beta \leq |\operatorname{\operatorname {Stab}}_K(A)|\), then \(\operatorname{\operatorname {Stab}}_{K^{\mathrm{StabC}(\beta )}} (A) = \mathbb {F}\).

If \(4 \leq |\operatorname{\operatorname {Stab}}_K(A)|\) and \(p^\beta \leq |\operatorname{\operatorname {Stab}}_K(A)|\), then \(\frac{p}2 \leq |\operatorname{\operatorname {Stab}}_{K^{\mathrm{StabC}_2(\beta )}}(A)|\).

For \(a \in \operatorname{\operatorname {Stab}}_K(A)\), we also have \(a^{-1} \in \operatorname{\operatorname {Stab}}_K(A)\).

If \(K \leq K'\) then \(\operatorname{\operatorname {Stab}}_K(A) \subseteq \operatorname{\operatorname {Stab}}_{K'}(A)\).

If \(1 \leq K\) implies \(K \leq K'\) then \(\operatorname{\operatorname {Stab}}_K(A) \subseteq \operatorname{\operatorname {Stab}}_{K'}(A)\).

If \(a \in \operatorname{\operatorname {Stab}}_K(A)\) and \(K \leq K'\) then \(a \in \operatorname{\operatorname {Stab}}_{K'}(A)\).

We have \(\operatorname{\operatorname {Stab}}_{K_1}(A) \operatorname{\operatorname {Stab}}_{K_2}(A) \subseteq \operatorname{\operatorname {Stab}}_{K_1 K_2}(A)\).

For \(a \in \operatorname{\operatorname {Stab}}_{K_1}(A), b \in \operatorname{\operatorname {Stab}}_{K_2}(A)\), we have \(ab \in \operatorname{\operatorname {Stab}}_{K_1 K_2}(A)\).

We have \(-\operatorname{\operatorname {Stab}}_{K}(A) \subseteq \operatorname{\operatorname {Stab}}_{K^3}(A)\).

For \(a \in \operatorname{\operatorname {Stab}}_K(A)\), we also have \(a \in \operatorname{\operatorname {Stab}}_{K^3}(A)\).

If \(p^\beta \leq |A| \leq p^{1 - \beta }\) and \(K {\lt} \frac{p^\beta }2\), then \(\operatorname{\operatorname {Stab}}_K(A) \neq \mathbb {F}\).

For \(n \in \mathbb {N}\) we have \((n+1) \cdot \operatorname{\operatorname {Stab}}_{K}(A) \subseteq \operatorname{\operatorname {Stab}}_{K^{8n + 1}}(A)\).

If \(4 \leq |\operatorname{\operatorname {Stab}}_K(A)|, p^\beta \leq |\operatorname{\operatorname {Stab}}_K(A)|, p^\gamma \leq |A| \leq p^{1 - \gamma }\) then \(\frac{p^\gamma }2 \leq K^{\mathrm{StabC}(\beta )}\)

We have \(\operatorname{\operatorname {Stab}}_{K_1}(A) - \operatorname{\operatorname {Stab}}_{K_2}(A) \subseteq \operatorname{\operatorname {Stab}}_{K_1^8 K_2^3}(A)\).

We have \(3 \operatorname{\operatorname {Stab}}_K(A)^2 - 3 \operatorname{\operatorname {Stab}}_K(A)^2 \subseteq \operatorname{\operatorname {Stab}}_{K^{374}}(A)\).

\(\mathrm{StabC}(\beta ) = 9 \mathrm{StabC}_2(\beta )\)

\(\mathrm{StabC}_2(\beta ) = 374^{\lceil \log _{\frac32}(1 / \beta ) \rceil }\)

For any two sets \(A, B\), we have \(|A-B| \leq \frac{|A+B|^3}{|A||B|}\)

For any set \(A\) and two values \(a, b\), we have \((a-b)A \subseteq aA - bA\).

Let \(A, T\) be finite sets with \(Q(A, \lambda A) \geq \frac{|A|^3}K\) for all \(\lambda \in T\). Then there exist sets \(A', T'\) with \(\frac{|A|}{16 K} \leq |A'|\) and \(\frac{|T|}{2^{17} K^4} \leq |T'|\), such that \(T' \subseteq \operatorname{\operatorname {Stab}}_{2^{110} K^{42}}(A')\).

For \(f : A \to B, G : A \to C\) we have \(f \# g\) is a function \(B \to C\) defined by \(f \# g(x) = \sum _{f(y) = x}g(y)\).

We have \(f \# (g + h) = f \# g + f \# h\).

\(\mathrm{id} \# f = f\)

if \((f \# g) (x) \neq 0\) then \(\exists y, f(y) = x\).

We have \(f \# (g - h) = f \# g - f \# h\).

We have \(h \# (f \# g) = (h \circ f) \# g\).

For any three sets \(A, B, C\), we have \(|A+B+C| \leq \frac{|C+A| |A+B|^8}{|A|^6 |B|^2}\)

The uniform distribution on a nonempty set \(A\), \(\operatorname{\operatorname {Uniform}}(A)\), assigns \(\frac1{|A|}\) to all values in \(A\) and \(0\) to other values.