File Sync without the Cloud

I had to share some large data files with a friend recently. As I was going through the list of usual options :
1. Opera Unite
2. Torrent sharing
3. Dropbox
4. Google Drive
5. wetransfer.com
6. justbeamit.com

I found no fast and cheap option. The painful thing about the good (fast) services is that they do not provide only sync across computers, but require you to upload data to their servers, which is both expensive and insecure.

I found an awesome software, Bitsync, that just works on any device. Yes, even my phone running android. No need to setup port forwarding or go through any tech hassles. And the best feature of all, it's FREE. It's also very fast. Usually when I had to resort to torrent-sharing the speed of download was very slow, but bitsync somehow finds the optimal path.

There are other companies that provide the same service. The best among them is aerofs . You wouldn't require it's paid services for most personal use. Here's a list of all such softwares on how-to-geek .

Counting

Much of information and coding theory involves counting and combinatorial reasoning. For example how many non-touching balls of unit radius can fit  in an n-dimensional space ${\mathcal{F}_2}^n$.  Combinatorial arguments come in very handy in these situations. The probabilistic method is another example of the kind of arguments I came across in information theory literature. One good non-technical example that changed the way I count is -

Q. Consider a group of  $2^6 = 64$ tennis players. These players are now matched pairwise and the losers are eliminated from the pool. From the remaining pool of victors, players are paired again and the process is continued. How many games are required to find a single winner?

A. 63

Method 1. One way (the straightforward method atleast before reading the alternate way) to compute the answer is to count the number of matches in each round i.e. 32 + 16 + 8 + 4 + 2 + 1 = 63.

Method 2. Realize that each match eliminates 1 player, hence to eliminate 63 players you need 63 matches.

Interesting Arguments

An interesting line of reasoning that I came across in my Combinatorial Theory  course is
the minimal element method.

The general outline of a proof using this method is as follows : Suppose you want to prove that a given set of elements satisfy a given property $P$. Let the set of bad elements not satisfying that property be denoted by $\mathcal{B}$. Assume that $b$ is the minimal element of $\mathcal{B}$ in some sense. Then using the assumptions of the claim, show that there exists  another element $b^\prime \in \mathcal{B}$ such that $b^\prime < b$.

Another interesting style of argumentation which is generally seen in information theoretic arguments is the probabilistic method in which a deterministic solution to a given problem is shown to exist by constructing a random candidate for a solution, and showing that this candidate solves all the requirements of the problem with positive probability.

Typesetting math equations in Latex

While writing any document in $\LaTeX$ using the amsmath package many wishes need to fullfilled. The most cumbersome task that troubles me frequently is typing the right and left delimitors (say \lvert \rvert) seperately. Why can't there be a command that does that on its own. Turns  out that somebody did write a package to improve upon amsmath : mathtools .

The most useful feature I found is, allowing the user to define paired delimitors For example, instead of typing,

    \left\{ \frac{a}{b+c} \right\}

You can just define paired delimitors and use them as follows,

    \usepackage{mathtools}
    \DeclarePairedDelimiter{\set}{\lbrace}{\rbrace}
    \set*{ \frac{a}{b+c} }

The output is the same as before,
$$\left\{ \frac{a}{b+c} \right\}$$

Using the * after the command resizes the delimitors to fit the vertical length of the expression.

Another interesting tool in this package is allowing tags for equations to have user-defined labels. See section 3.2.2 in  mathtools .

Another great tool for publishing documents on the web is mathjax. Recently mathjax allowed users to use mathjax scripts through their plugins on popular web platforms. 

Subadditivity, Limits and Lim Inf

Consider a sub-additive sequence $a_n$ for $n \geq 1$, where sub-additivity is defined as follows :
$$a_{n+m} \leq a_n + a_m$$

Fekete's Lemma says that for any such sequence $\lim_{n \rightarrow \infty} a_n/n = \lim \inf_{n \rightarrow \infty} a_n/n $, which can be easily proved. The proof is as follows-

Let $\lim \inf_{n \rightarrow \infty} a_n/n  = l$. Therefore, $\exists K$ s.t.
$$\left\vert \frac{a_K}{K} - l \right\vert = \epsilon/2$$

Now consider a large enough $L$ such that $ \frac{a_r}{KL} < \epsilon/2, \forall  r < K$. Thus, for every $n \geq KL$ we can write $n$ as $n = Kq + r$, where $q \geq L$ and $r<K$. Therefore,

\begin{align}
\frac{a_n}{n} & \leq \frac{q a_K}{Kq+r} + \frac{a_r}{Kq+r} \\
                        & \leq \frac{q a_K}{Kq} + \frac{a_r}{Kq} \\
                        & \leq \frac{a_K}{K} + \frac{a_r}{Kq} \\
                        & \leq  l + \frac{\epsilon}{2} + \frac{\epsilon}{2}\\
\end{align}

Since this is true for all $n > KL$ the limit exists and is equal to $l$. An alternate but similar proof is given here.

Pairwise Independence, Mutual Independence and Coding Theory

Consider a set of variables $\{X_1, X_2, ..., X_n\}$. A pair of variables $X_i, X_j$ are pairwise independent  iff $P(X_i,X_j) = P(X_i)  P(X_j)$. And any subset $A_k =\{X_{i_1},X_{i_2},...X_{i_k}\}$ of random variables is mutually independent if

                            $P(X_{i_1},X_{i_2},...,X_{i_k}) = \prod_j P(X_{i_j}) $

Bernstein gave an example of a set of random variables, of which any two are pairwise independent, but the set as a whole is not. A general class of examples which can be easily constructed from this set is the following -

$X_1 = A_1$
$X_2 = A_2$
$X_3 = A_3$
$\vdots$
$X_k = A_k$
$X_{k+1} = A_1+A_2+...+A_k$

where $A_i$'s are a set of i.i.d. mutually independent random variables, uniformly distributed in $\mathbb{F}_2$. Now it can be easily seen that any size $k$ subset $S_k$ of  $\{X_1, X_2, ..., X_{k+1}\}$ is a mutually independent set, but the $k+1$  set  $\{X_1, X_2, ..., X_{k+1}\}$  has a degenerate probability distribution given $A_k$ i.e.
                               $P(X_1, X_2, ..., X_{k+1} | A_k) \in \{0,1\}$

Now one can observe from the example that this is an example of parity check codes (wiki).  Also it is easy to observe that parity check codes are MDS codes. (wiki)

Now, given a general set of $n$ random variables which is $k$ independent (any $k$ subset is mutually independent) is it possible to construct an MDS code from these?

I give below conditions in which MDS code are constructable :

• The random variables $X_i$ are uniformly distributed in a field $\mathbb{F}_q$.
• The set $A_n = \{X_1, X_2, ..., X_n\}$ is $k$ independent i.e. any $k$ subset $A_k$ is mutually independent
• The probability distribution of $A_n$ given $A_k$ is degenerate i.e.

                                                    $P(A_n | A_k) \in \{0,1\}$

Now, given these conditions it can be easily seen from the proof of the Singleton bound (for general non-linear codes) that $\{X_1, X_2,...,X_n\}$ is an MDS code [length, information bits, min. distance] = $[ n, k, n-k+1]$.

Pirates, treasure, and data security

Suppose you have a file that you want to divide between $n$ users. Now the division should be such that whenever any $k$ of the $n$ persons collaborate they know the complete file otherwise they must not have any information about the file.

Interestingly the solution to this problem is related to the solution to the following problem :

Thirteen pirates go on an extended voyage, pillaging and plundering from Africa to Asia. By the end they have quite a stash--too much to take back with them. They decide to lock it in a chest, leave the chest on an island, and come back for it a year later. Of course, not being terribly trusting, they want to ensure that none of them can come back early and claim the treasure for himself. They could just put 13 locks on it and each take a key, but a pirate's life is dangerous--they may not all be around in a year. What they want is for any majority of the original thirteen to be able to open the chest, while any fewer will be locked out. How many locks will it take for them to achieve this? The locks they are using are quite simple. Each key opens only one lock (no master keys), but keys can be duplicated, so multiple pirates can have keys to the same lock.

Solution1:

For the pirate problem you should choose ${n \choose {k-1}}$ locks and distribute the keys such that for every group of ${k-1}$ users there is a lock that they do not have the key for.

This solution easily extends to the first problem. Let the data file be $x \in \mathbb{F}_q$. Now generate ${n \choose {k-1}}$ random variables $R_i, i \in \{1, \ldots, {n\choose {k-1}}\}$ and give each user the information $x + \sum_{i=1}^{n \choose {k-1}} R_i$. Now, the values of the random variables can be distributed like the keys of the lock in the previous puzzle, and we are done.

Solution2:

This is the solution proposed by Adi Shamir (the guy behind Bitcoins), here.

Basic Idea : If you are given any $k$ points of a $k-1$ degree polynomial $f(x)$, you can determine the polynomial. So,

secret := polynomial coefficients
user data := $n$ points of the polynomial

Ofcourse, the polynomial is over a finite field. You need only $k$ random variables in this scheme to share one bit ($a_0 = [x^0] f(x)$) instead on ${n \choose (k-1)}$ in the previous scheme.