Color Theme
Theme§
Colors§
Fonts§
SVG Samples§
Illustration§
TikZ§
GoAT§
Hypergraph Decomposition§
The Romanian Travelling Salesman§
Text Samples§
This section contains text samples to test out the color theme.
Blocks§
Definition§
Wiener chaos expansion
The Wiener chaos expansion, also known as Polynomial chaos, is a representation of random variables in terms of a polynomial function of other random variables.
Sps. $\mathbf{X}$ is a random vector with a Gaussian distribution. The $i$th degree Hermite polynomials $H_i$ are orthogonal to the Gaussian distribution in one-dimension, and are the polynomial basis. Then, we get that $\mathbf{X} = X$ and the Wiener chaos expansion of $Y$ is given by
$$ Y = \sum_{i \in \mathbb{N}} c_i H_i(X). $$
Example§
Dyck Paths
A Dyck path is a staircase walk from $(0, 0)$ to $(n, n)$ that is below or on the diagonal line $y = x$
$$ \newcommand{\arraystretch}{1.5} \begin{array}{| c | c | c | c |}\hline \ \ & \ \ & \ \ & \blacksquare \\\hline & \ \ & \blacksquare & \blacksquare \\\hline \ \ & & \blacksquare & \\\hline \blacksquare & \blacksquare & \blacksquare & \ \ \\\hline \end{array} $$
Theorem & Proof§
Tits Alternative
Let $G$ be a finitely generated linear group over a field, then one of the following conditions are true
- $G$ has a solvable subgroup with finite index,
- or it contains a nonabelian free group.
Miller-Rabin Test
Let $p$ be an odd prime, $r = p - 1$, $k, q$ be values that satisfy $r = 2^k \cdot q$, and $a \in \mathbb{Z}$ such that $p \nmid a$.
Then, one of the following conditions are satisfied
- $a^q \equiv_p 1$
- One of $a^q, a^{2q}, a^{4q}, \dots, a^{2^{k-1}q}$ is congruent to $-1$ modulo $p$.
By Fermat’s little theorem, we know $a^{p-1} \equiv_p 1$. Hence, $a^{2^{k-1}q} \equiv \pm 1$. If this value is $1$, then $a^{2^{k-2}q}$ is also, and so on. If $a^{2^l q} \equiv_p 1$ holds for all non-negative $l$ strictly less than $k$, then the first statement holds. Otherwise, there must exist an $l$ such that the second statement holds.
Inline Code§
The BigInt::naive_multiplication() function described below is found in my cryptography repo. It is an $\mathcal{O}\left(n^2\right)$ algorithm, which is not ideal for very large integers. If the number of “groups” in a BigInt is $\gtrapprox 80$ groups then we can move onto the Karatsuba algorithm which has a better asymptotic runtime of $\mathcal{O}(n^{1.58})$.
Code Block§
BigInt naive_multiplication(BigInt const& x, BigInt const& y)
{
if (y.groups() == 1)
return naive_multiplication(x, y.m_groups.back());
auto z = std::deque<uint32_t>(x.groups() + y.groups() + 1);
auto carry = uint64_t {};
for (auto i = 0; i < x.groups(); i++) {
carry = 0;
for (auto j = 0, k = i; j < y.groups(); j++, k++) {
auto product
= static_cast<uint64_t>(x.m_groups[i])
* static_cast<uint64_t>(y.m_groups[j])
+ z[k]
+ carry;
z[k] = static_cast<uint32_t>(product);
carry = product >> 32;
}
z[i + y.groups()] = carry;
}
emsmallen(z);
return { z };
}
$\LaTeX$§
Array§
$$ \newcommand{\arraystretch}{1.1} \newcommand{\dw}[1]{\downarrow\!{\scriptsize\text{#1}}} \footnotesize \begin{array}{| c c c c c c c c c c c c c c c c |}\hline 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 &35 & 36 & 37 & 38\\\hline 36 & 83 & 132 & 183 & 236 & 291 & 348 & 407 & 468 & 531 & 596 & 663 & 732 & 803 & 876 & 951\\ \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & & \dw{2} & \\ 18 & 83 & 66 & 183 & 118 & 291 & 174 & 407 & 234 & 531 & 298 & 663 & 366 & 803 & 438 & 951\\ \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & & \dw{4} & \\ 9 & 83 & 33 & 183 & 59 & 291 & 87 & 407 & 117 & 531 & 149 & 663 & 183 & 803 & 219 & 951\\ \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} & & \dw{3} & \dw{3} \\ 3 & 83 & 11 & 61 & 59 & 97 & 29 & 407 & 39 & 177 & 149 & 221 & 61 & 803 & 73 & 317\\ \dw{9} & & & & & & & & \dw{9} & \dw{9} & & & & & & \\ 1 & 83 & 11 & 61 & 59 & 97 & 29 & 407 & 13 & 59 & 149 & 221 & 61 & 803 & 73 & 317\\ & & \dw{11} & & & & & \dw{11} & & & & & & \dw{11} & & \\ 1 & 83 & 1 & 61 & 59 & 97 & 29 & 37 & 13 & 59 & 149 & 221 & 61 & 73 & 73 & 317 \\\hline \end{array} $$
Fractions§
$$ \newcommand{\arraystretch}{2} \begin{array}{r c} \texttt{\small \textbackslash displaystyle} & \genfrac{(}{)}{}{0}{a}{b}\\ \texttt{\small \textbackslash textstyle} & \genfrac{(}{)}{}{1}{a}{b}\\ \texttt{\small \textbackslash scriptstyle} & \genfrac{(}{)}{}{2}{a}{b}\\ \texttt{\small \textbackslash scriptscriptstyle} & \genfrac{(}{)}{}{2}{a}{b} \end{array} $$