# Forkable Strings are Rare

In a blockchain protocol such as Bitcoin, the users see the world as a sequence of states. A simple yet functional view of this world, for the purpose of analysis, is a Boolean string $w = w_1, w_2, \cdots$ of zeros and ones, where each bit is independently biased towards $1$ favoring the “bad guys.”

A bad guy is activated when $w_t = 1$ for some $t$. He may try to present the good guys with a conflicting view of the world, such as presenting multiple candidate blockchains of equal length. This view is called a “fork”. A string $w$ that allows the bad guy to fork (with nonnegligible probability) is called a “forkable string”. Naturally, we would like to show that forkable strings are rare: that the manipulative power of the bad guys over the good guys is negligible.

Claim ([1], Bound 2). Suppose $w =w_1, \cdots, w_n$ is a Boolean string, with every bit independently set to $1$ with probability $(1-\epsilon)/2$ for some $\epsilon < 1$. The probability that $w$ is forkable is at most $\exp(-\epsilon^3n/2)$.

In this post, we present a commentary on the proof that forkable strings are rare. I like the proof because it uses simple facts about random walks, generating functions, and stochastic domination to bound an apparently difficult random process.

# Some Facts about the Gambler’s Ruin Problem

Consider a random walk in the two-dimensional discrete space, where the horizontal direction is indexed by nonnegative time steps and the vertical direction is indexed by integers.

A particle is at its initial position $z > 0$ at time $0$. At every time step, it independently takes a step up or down: up with probability $p$ and down with probability $q = 1-p$. If $p = q$ the walk is called symmetric. Let $p_z$ and $q_z$ be the probabilities that the particle ever reaches some level $a >z$ or $0$, respectively. When it does, the walk stops. The quantity $q_z$ is the ruin probability. We set the initial conditions as $q_0 = 1, q_a = 0$.

The Gambler’s Ruin Problem: What is the probability that a walk, starting at some $z > 0$, eventually reaches the origin?

# Vandermonde Submatrices and Arithmetic Progressions

[This post, which is based on an ongoing discussion with Alex Russell and Ravi Sundaram, contains some unpublished results.]

Currently, we are asking whether all submatrices of the order-$p$ Vandermonde matrix over a finite extension of $GF(2)$ are invertible where $p$ is prime. The answer is “no” in general: there are examples of fields where the Vandermonde matrix has a singular submatrix.

We can ask an easier(?) question, though. What happens if we randomly sample a set of columns and look into submatrices formed by a subset of the sampled columns. With a touch of beautiful insight, Professor Russell has connected Szemeredi’s theorem on arithmetic progressions with this question.

Let $AP_k$ denote an arithmetic progression of length $latek k$. Let $[N] := \{1, 2, \cdots, N\}$ for $N \in \mathbb{N}$.

The Szemerédi theorem says, any “sufficiently dense” subset $S \subset [N]$ contains infinitely many $AP_k$ for all $k \in \mathbb{N}$. A finitary version says: Fix your favourite $k \in \mathbb{N}, \delta \in [0, 1]$. Then,  there exists a natural $N := N_{k, \delta}$ such that if you look any subset $S \subset [N]$ of size at least $\delta N$, you will find an $AP_k$. Yet another version says:

Szemerédi’s Theorem. The size of the largest subset $S \subset [N]$ without an $AP_k$ cannot be too large; in particular, it is $o(N)$.

Recall that a function $f(x)$ is $o(g)$ if it grows too slow compared to $g(x)$, so that $\lim_{N\rightarrow \infty}{f(x)/g(x) = 0}$.

Featured

# Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code

To this day, no method of finding a generator of $Z_p^*$ is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of $Z_p^*$.Keith Conrad

An $n$th root of unity in a finite field $F$ is an element $r \in F$ satisfying $r^n=1$, where $n$ is an integer. If $n$ is the smallest positive integer with this property, $r$ is called a primitive $n$th root of unity. If $r$ is a primitive $n$th root of unity, then all elements in the set $\mu_n = \{1, r, r^2, \cdots, r^{n-1}\}$ are also roots of unity. Actually, the set $\mu_n$ form a cyclic group of order $n$ under multiplication, with generator $r$.

Problem: Suppose you are given a finite field $F=GF(2^d)$ of degree $d$, and you are promised that there indeed exists a primitive $p$th root of unity $r\in F$ for $p$ prime. Find $r$, and in particular, produce a C++code that finds it.

In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.

# Spectral Sparsification by Spielman and Srivastava: How They Connected the Dots

In this post, I will discuss my own understanding of the spectral sparsification paper by Daniel Spielman and Nikhil Srivastava (STOC 2008). I will assume the following:

1. The reader is a beginner, like me, and have already glanced through the Spielman-Srivastava paper (from now on, the SS paper).
2. The reader has, like me, a basic understanding of spectral sparsification and associated concepts of matrix analysis. I will assume that she has read and understood the Section 2 (Preliminaries) of the SS paper.
3. The reader holds a copy of the SS paper while reading my post.

First, I will mention the main theorems (actually, I will mention only what they “roughly” say).