Mass MOCA and combinatorics

Consider the installation on the right in the picture above. If we label each color with a number, then each square represents a permutation. Each square is now grouped into a group of 4 squares, as shown below. Each group has an interesting property. If you superimpose any two of the squares in the group, none of the colors will collide.

 

Now if we represent each permutation as a vertex of a graph such that two vertices are adjacent iff they collide. Then the largest independent set in the graph is of size 4.  There are 4! = 24 such possible independent sets (order dependent). And all 24 groups are shown in the art installation.

Random Conversations

Watched this speech by MP Hukumdev Narayan.



It reminded me of this conversation between me and my friend K. K is an economist studying for his PhD.

We were at a bar near the university.

Me : Why do you think Americans spend so much money on alcohol

K :  Americans spend money on travel, alcohol and girls. Indians on the other hand like to save up.

Me : But..  that saved money has to be spent eventually...

K : You have to save for emergencies  in India.

Me : hmm... but I don't think, medical or other emergencies are that big of an expenditure most of the time. Where does the money go ?

K : Food ? ... Nope.

Me : Weddings!!

K (laughs) : Yeah. Fat Indian Weddings.

Me : Yes. There should be a law on expenses in weddings.

K : There should be a law imposing restrictions on expenses in general.

Air Play using a raspberry pi

Instructions specific to OS X:

1. Download the image for Raspbian from : raspberrypi.org/downloads.

2. Install this image on the SD card using the app : app for macbook

3. Connect the raspberry pi (RPi) to your router with an ethernet cable and you should be able to ssh into it with the ip form the router's config page, which is 10.0.0.9 for me.

3. Enable wifi so that the RPi can use the WiFi Dongle. Also setup the RPi to receive DLNA content : Stephen Philips Blog

4. Connect the RPi to you speakers and install BubbleUPnP app on android to be able to play music form your phone including from mobile apps like Google Music.

5. Install a media server that streams media over the network. Now to be able to discover your RPi on the network and push DLNA content to it you would have to install another software. I Installed Plex and LINNOSS (Kinsky) to play music from my computer.

Enjoy wire-free music!

Vandermonde Matrix

I was recently trying to prove that a Vandermonde type of matrix is full rank and a quick google search did not give me the the proof I had in mind. So here it is,

Consider a matrix of the form,
\begin{equation}
\begin{bmatrix}
1& \alpha_1& \alpha_1^2& \ldots& \alpha_1^{r-1}\\
1& \alpha_2& \alpha_2^2& \ldots& \alpha_2^{r-1}\\
\vdots \\
1& \alpha_r& \alpha_r^2& \ldots& \alpha_r^{r-1}\\
\end{bmatrix} = [\mathbf{a_0} \ldots \mathbf{a_{r-1}}]
\end{equation}

If this matrix is not full rank then there exists coefficients $c_0, c_1, c_2, \ldots, c_{r-1}$ such that $\sum_i c_i \mathbf{a_i} = \mathbf{0}$. Therfore  there exist $r$ roots $\alpha_1 \ldots \alpha_r$  of the polynomial $\sum c_i x^i$ of degree less than $r$.

Macbook, Sublime Text and IPython : the best combo for a coding project

I recently switched to a mac so I may be a a bit over-zealous, but my macbook is the first computer that I like to work on. It doesn't get stuck, has extensive command line features, is highly customizable, and has a great retina display.

In the past whenever I got a new computer the enthusiasm lasted not more than a week. It may be that I have discovered the right set of tools to work with, this time, but I never really had so much ease in coding in a language other than MATLAB and it's not that I haven't done projects in other programming languages. The combination of IPython's great debugging features, OS X's superb command line iterm and Sublime Text's easy text manipulation and great plugin's has made my life easier by a great deal.

So I'll try to make a quick reference for my future self who has a tendency to forget things quite a lot.

OS X tools 

Iterm :

• You can divide the terminal into mutiple windows like terminator. Use Cmd+d and Cmd+Shift+d to divide the current tab.
• You can re-assign keys to move quickly on a line  : link

I have re-assigned the left option key to Esc from Preferences > Profiles > Keys > Left Option Key Acts as. Now, in addition to the usual bash line navigation Ctrl+a, Ctrl+e, etc. , I can move one word left and right using Option+f and Option+b respectively. I can also delete word by word forward and backwards using Option+d and option+delete without trying to stretching my hand across the keyboard.

Caffeinate:
With windows, I was extremely irritated when the following happened. You are just about to head out but you suddenly remember you haven't checked your email. You open up your laptop to quickly find out your venue (because you are too lazy to remember everything), so that you can catch the bus arriving in two minutes outside your apartment. But Windows decides that there's a dangerous virus that you cannot be not-protected from and you have to wait for an hour for the software updates to finish before you can check your email.

Thankfully this doesn't happen with my macbook, because in addition to not being extremely irritating, it's battery lasts long enough  (atleast for now) for you to check your email and not have to look for a power socket, which is partly because OS X has a very aggressive power save mode. Which is fine until you are want to connect your laptop to your TV and watch a TV show without having to get up and move the mouse every few minutes.

caffeinate <command> is helpful in this scenario.

iBooks and the default OS X dictionary:
I like to have a dictionary around whenever I'm reading anything, which is too much effort for when you are reading a soft copy.


Menu Search:
Looking through the online documentation of a software to find out exactly where the option you want to set resides, is too much trouble especially considering the fact that it's easier for you to go through Petabytes of data on another computer (google's server farms) than to look at a mere 100s of bytes you have on your computer. That is why the help menu search keyboard shortcut Cmd+Shift+/ is one of my frequently used key strokes.

Sublime Text

There's nothing to document since the text editor's documentation is easy to find and it's easy to configure. Here are the plugins that I have installed in my Sublime Text 3, in decreasing frquency of usage (in addition to the in-built command palette features)-

• Origami
• Bracket Highlighter
• SublimeCodeIntel
• Text Pastry
• WhoCalled
• Advanced New File

IPython debugging 

pdb is a great debugging tool, but one flaw of debugging with these tools is that to set a breakpoint to get to the one case that isn't working you have to go step through the hunderds of cases that are  and it get too tedious. And that's why I preferred to use print statements to debug.

Now, enter the python modules logging. So here's what every piece of code I write now looks like -

try:
function_to_debug()
except Exception:
logging.exception("here")
_breakpoint()  # 0fa1ab74

The  logging module let's me know where exactly the exception was raised and the breakpoint let's me examine the variables values at that point. So I write my code without too much worrying about the extreme cases, and handle them as and when  they arrive.

People have also extended the logging module to print colored output. I'm too lazy to google for that now, but that would be a killer tool for any debugging task.

There's also the %pdb IPython magic feature which is essentially the same thing, except for the logging.exception("here") line above.

Note to self : keep adding rambling and features to this.

Git : Quick Reference

Get Started

To get started with git read the first two chapter in git documentation. I think after the first two chapters it would become useless to  keep reading, instead just keep learning as you go. Use git help <command> to learn more about a command or just google. If you still want to keep reading look at the reference URLs at the end.

To create a local git repository read git-basics. You can use any remote computer as a server very easily with git. Just create a git repository and then clone it from another computer using

git clone <username>@<IP>:<path/to/.git>

Git will use ssh to login and copy the files so no extra setup is needed. The instructions at  git-basics show how to create a git repository without a name, but if you want to give a name to you git repository i.e. instead of just a .git folder you want myrepo.git you can do :

mkdir myrepo.git 

cd myrepo.git 

git init --bare

Add remote repositories with

git remote add [shortname] [url]

Configurations

• color your diffs

git config --global color.ui auto

• more configuration options git-scm

Working with git

Working with Remotes

Use the following command to create and track remote branches (ref)

git checkout --track -b <local branch> <remote>/<tracked branch>
OR
git checkout -t <remote>/<tracked branch>

The second command keeps the same name as the remote tracked branch. To avoid the default merging with a remote branch with git pull  use git fetch 

git fetch <remote>OR
git fetch --all

to fetch from all remotes. You can then checkout a branch and fast forward using

git merge --ff-only <remote>/branch

Reverting to old commits

Look at the reset command.

git checkout <branch>~n checkout the commit n commits before the latest commit

git checkout <commit> <file1> <file2>...  checkout files form commit

Note: <commit> can be a branch name or the checksum of any commit.

Looking at the commit logs

Look at diff and status.

git diff <branch old/commit checksum>:[<file>] <branch new/commit checksum>:[<file>]

to see the difference in the files. To see commit log with only the names of the changed files do

git log --name-only

Useful : git log -p -n shows the changes introduced in the last n commits. Use gitk --all to see everything in a gui.

Branching

Show all branches

git branch -a

Create branch on the current state

git branch <name>

Git Stash

Use git stash to quickly save your current state without messing up your commit history

git stash save "<message>"

You can also do multiple layers of stashes. So list all the stashes you have done using

git stash list
stash@{0}: On shoulda: Updating instructions
stash@{1}: On master: started merge but need to fix #104 first
stash@{2}: On feature1: Adding some stuff

Pop the stash from your commit and get back to the state before "git stash save".

git stash pop/apply

A note with this command, it deletes that stash for good, while "git stash apply" does not. You can manually delete stashes with:
git stash drop <id>

and delete stashes with

git stash drop <id>

or delete all of the stored stashes with:

git stash clear

URLs :
a. http://gitready.com/beginner/2009/03/13/smartly-save-stashes.html
b. http://gitready.com/beginner/2009/01/10/stashing-your-changes.html

Renaming branches

Refer to here

Now to rename the master branch you have first change the default head to something else on the remote. You cannot do this from the client. First ssh onto your server and do 

git symbolic-ref HEAD refs/heads/new_master

Now, you can do as you want.

Frequently Used Commands 

• git add    add files to git tracking
• git commit   commit the files to the local git
• git push    update the remote with the current branch
• git pull   fetch and merge current branch from remote origin
• git fetch    fetches named heads or tags from one or more other repositories, along with the objects necessary to complete them.
• git fetch --all   fetch from all remotes
• git merge  incorporates changes from the named commits (since the time their histories diverged from the current branch) into the current branch.
• use "git merge --ff-only <remote>/branch" to fetch and merge from remote 
• git branch <name>  creates a branch at the current checkout
• git log  show commit logs for the current branch
• git checkout <file OR branch OR branch:file> Checkout files and branches

Reference URLs

http://git-scm.com/doc
http://gitready.com

Simple explanation of cryptography

Suppose you want somebody to send you a number $x \in [1,n-1]$ such that any eavesdropper does not know what the message is. The simplest way to do that is have them send $f(x)$ to you, where the function $f(.)$  is injective.

But if the function is easily invertible then anybody who knows what $f(.)$ was used can easily eavesdrop and decode the secret message. So, you can either keep $f(.)$ secret, or you can make the inversion of $f$ really difficult except for you. The latter technique is the one modern crypto-systems use and the former one was used in ancient times starting with Caesar. The problem with Caesar's technique if that sender and the receiver have to agree on what $f(.)$ has to be used and that communication has to be secure, thus the problem remains.

The main idea in modern cryptography is that you should find a function that only you can invert. This is based upon the difficulty of factoring large primes. Suppose that the function $f_n(.)$ can be inverted easily only when the factorization of $n$ is known. Now given such a function $f_n(.)$ you can secretly choose large primes and compute a number $n$ as the product of those primes. Now, since you know the factorization of $n$ the inversion is easy for you, but not for anybody else.

Since the sender does not need to know the factorization of $n$ to encode, your communication becomes secure.

Richard Hamming : Intro to art of doing science and engineering, Lecture 1

History has taught us much about the progress of science. Human knowledge has been growing at an exponential rate since Newton. There are about 10,000 different field of science now, about that much more than there were in the 1700's during Newton's time. Continuing in this fashion and assuming that the number of scientists grows with the amount of knowledge in 300 years there should be about a billion different fields of science and every man on earth would be a scientist. Obviously, this cannot happen. History is not a perfect predictor of the future. Consider how different history would have been if either of Napoleon, Einstein or Hitler had died young. There are too many little things that change too much.

Although the number of scientific fields may not grow exponentially, human knowledge would continue to grow. You would have to learn much more than your ancestors had to do to be able to contribute to anything. And therefore you have to learn how to learn. To adapt your style and not just depend upon history. Having a good style or approach towards learning or knowledge  is the best way to keep up. But you should keep in mind that there is no unique style that fits all. A good criterion is  to cling to fundamentals. But, you have to know how to define fundamentals which is difficult, because they change frequently.

Another important thing to know is, without a vision of where you are headed you are no better than a wandering drunk. The first ingredient of great work is having a goal and working towards it. It doesn't matter what that goal is as long as you believe in it and work hard towards it. Otherwise you would just keep drifting through life. To make your life's contribution add up to something a goal is very important.

To be able to contribute, you should keep an open mind. Knowledge is not fundamentally divided into tight departments. It is a homogenous thing. And knowing the relations between different fields can help you a lot.

You should also note that computing is the future of science, because of the following fundamental reasons -

• speed - neurons function at about a 100m/s vs light which travels at 3e8m/s
• precision 
• reliability - we trip and stumble even after walking for decades
• rapidity and control - we can only process only about 50bits per second
• boredom
• cost - humans are getting expensive and machines are getting cheaper

Finally, you have only one life. You ought to do more than just get by. You have to have a goal. Although, achieving a goal is not the best part, the struggle is. The struggle to achieve excellence is worth the struggle.

Your  life is not the sum total of the pleasant moments in it. You cannot just get up and say to yourself "I shall be happy today", and get on with your day. The way to make your life truly happy is to struggle to be the kind of person you wish to be, to struggle for the goals you want to achieve and to be more articulate than just idle drifting like a drunken sailor. As Socrates once said, "An unexamined life is not worth living".

Primality Testing and importance of the twin prime conjecture

I have not studied the literature on primality testing or prime factorization but still I often wonder about the complexity of the algorithm that keeps the whole world secure.

Consider any interval of length $N$ on the real line. For $N=2$ we know that  we would not encounter more than one prime in any interval of length $N$. Now, intuitively I feel that this should be true for any number $N$, eventually i.e. there should exist a limit $L$  such that for all intervals $[n,n+N]$ for every $n>L$ there can exist only one prime in that range. Thus primes should become increasingly sparse (in this strong sense). Even though this result does not guarantee to reduce the complexity of finding prime numbers, it feels that it should make my job easier.

But alas, the twin prime conjecture lays fail to all of the above. Recently a professor proved a weaker version of the twin prime conjecture. He showed that for a given finite number $M$ (~ 7 million ) there are infinitely many prime pairs with difference less than $M$. Now people have improved upon his results and brought down the number $M$ to ~ 600, but it seems unlikely that the twin prime conjecture could be proven using his methods. Nevertheless, even this result re-inforces the difficulty of finding prime numbers.

A Christmas Gift to Myself : Raspberry Pi

Here are some ideas me and my friend Mohit are going to implement when our Raspberry Pi's reach us -

1. Personal search engine : I have a big collection of ebooks and publications I constantly need to query. So, putting its search index on a webserver would make it accessible to me everywhere and thus fasten up my research quite a lot. I'm going to use recoll for the PSE.
2. Bit Torrent Sync - Personal data back-up server.
3. Social network data mining - Using facebook and gmail API this could be easily implemented. Although, I need to find more open source algorithms to run. I am also open to implementing research algorithm [1]. Looking for suggestions here.
4. Mint Server (mint.com) - My bank sends me alerts after every successful transaction. This makes it easy to implement my own mint.com server and also a splitwise.com.
5. Bitcoin mining 
6. Tor server - This was Mohit's idea. This reminds me of  Oscar Wilde's quote.
7. A personal home music server (Mohit's idea)
8. A live twitter feed monitoring and LED lighting - something on these lines.

I'm also going to get a Raspberry Pi camera module. It would be nice to create a compressed time-lapse video. I need more suggestions here too.

PS : comments and suggestions required.

Hacking Dropbox

Having spent a lot of time finding tools for file syncing without a cloud and those that would work behind proxies, I decided to write my own Dropbox app to synchronize data across computers.

But Dropbox already does that. The point is to be able to do that using the free 2GB space that Dropbox provides. The motivation is that this way the synchronization should work behind every network routers (which must not block dropbox) that blocks torrent data. (ofcourse you can also avoid that using SSH tunneling).

So I decided to register a Dropbox developer app and use the Dropbox API to synchronize files using only the free 2GB storage. The only constraint now is that the individual files cannot be more than 2GB, but that is easily solved by breaking up the file using rar. Note that, the same could be done using Google Drive which provides 15GB of free space.

The Dropbox API documentation is very neat. I used the core Dropbox API with full access to user data for this app. The code below just authenticates the app to allow access to the user account. Once provided the authentication is then saved to a file, which when detected is used again.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

import dropbox import email, imaplib, os import urllib2 ##sign in to DROPBOX app_key = '<key>' app_secret = '<secret>' flow = dropbox.client.DropboxOAuth2FlowNoRedirect(app_key, app_secret) app_auth = False # set to false initially if os.path.exists('accesstoken'): app_auth = True if (app_auth == False): ### authorize server authorize_url = flow.start() print '1. Go to: ' + authorize_url print '2. Click "Allow" (you might have to log in first)' print '3. Copy the authorization code.' code = raw_input("Enter the authorization code here: ").strip() access_token, user_id = flow.finish(code) ## save access token once f = open( 'accesstoken', 'w' ) f.write( access_token ) f.close() else: f = open( 'accesstoken', 'r' ) access_token = f.read() f.close() client = dropbox.client.DropboxClient(access_token) print 'linked account: ', client.account_info()

The server and client communicate uses gmail. When the server uploads a file it emails the client the share link for the data. The client continuously monitors it's mailbox. As soon as it receives an email from the server, it downloads the data and sends back an acknowledgement mail. The server receives the acknowledgement, deletes the previous file, uploads another and sends the share link to the client again.

1 2 3 4 5 6 7 8

##sign in to GMAIL user = "<server>" pwd = "<password>" m = imaplib.IMAP4_SSL("imap.gmail.com") m.login(user,pwd) m.list() m.select("inbox")

Here's how I implemented the rest of it (thanks to these webpages 1, 2, 3) . The script for the client side would be similar

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

##main for loop while True: resp, items = m.search(None, 'TO', '"<server>+python@gmail.com"') items = items[0].split() print items emailid=items[-1] resp, data = m.fetch(emailid, "(RFC822)") email_body = data[0][1] mail = email.message_from_string(email_body) if mail['Subject'] == "done" ##delete file client.file_delete('/'+os.path.basename(uploadfilepath)) ##ask for another file (or just read from a file list) to upload directory in dropbox = main uploadfilepath = raw_input("enter (absolute) path to file").strip() uploadfile = open(uploadfilepath) response = client.put_file('/'+os.path.basename(uploadfilepath), uploadfile) print "uploaded:", response ##create share link sharelink = client.share("/"+os.path.basename(uploadfilepath), False) print sharelink['url']+" "+sharelink['expires'] ##send email from send_email import mail mail("client+python@gmail.com", sharelink['url'], "") print "email sent" time.sleep(25000)

The send_email script called above is the following :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

import smtplib from email.MIMEMultipart import MIMEMultipart from email.MIMEBase import MIMEBase from email.MIMEText import MIMEText from email import Encoders import os gmail_user = "<id>@gmail.com" gmail_pwd = "<passwd>" def mail(to, subject, text): msg = MIMEMultipart() msg['From'] = gmail_user msg['To'] = to msg['Subject'] = subject msg.attach(MIMEText(text)) #part = MIMEBase('application', 'octet-stream') #part.set_payload(open(attach, 'rb').read()) #Encoders.encode_base64(part) #part.add_header('Content-Disposition','attachment; filename="%s"' % os.path.basename(attach)) #msg.attach(part) mailServer = smtplib.SMTP("smtp.gmail.com", 587) mailServer.ehlo() mailServer.starttls() mailServer.ehlo() mailServer.login(gmail_user, gmail_pwd) mailServer.sendmail(gmail_user, to, msg.as_string()) # Should be mailServer.quit(), but that crashes... mailServer.close()

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.

A chess post

To improve one's chess play, reading books and famous games is an established but boring way to improve your skill. So I have resorted to playing continuously instead  which is far more entertaining but also far slower. Since the last month I started playing I have played 500 (!!) 10 min games on chess.com .

Occasionally I look at famous games. My amateur chess expert has advised me to look at the games of Paul Morphy first. I started looking at the games but then I realized that although improving is only possible when you analyze games, it is far more rewarding and easier to analyze your own games. I played this interesting chess game  recently. I am going to analyze my own and my opponent's mistakes from the principles I have gathered. Please post improvements/suggestions in comments.

Also since its turning out to be very difficult to include a dynamic chess board on blogger, I am just including the link to the game here : game?id=561308873 .

I am playing white in the above game. The winner makes the last mistake here, as always.

Black's second move seems intimidating. The bishop on b4 pins my d4 pawn. I don't know what the best defense to this is, so I move my knight and hope to quietly slip my bishop in d2 as in move 5. (I don't want the bishop to take my knight and destroy my pawn structure).

Normal development follows till move 9. White's 9. o-o is weakening. Black could have played 9. .. Bxc3, and after that 10 .. Bxe2. To defend that white should have played 9. Nd5 forking the Queen and the bishop.

Black's Queen remains on the open e-file for too long for white to play tactics such as 11. Bxa6 . Black's move 16 is also restricting. Qf5 would be better since it maintains pressure on the d4 square while providing the Queen room to move. Similarly white 17. Qe1 should have been Qe2, since it backs both the white knight and bishop.

A better move for white instead of 18. d5 would be Bd5.

Now 24. Ne5 leaves black  with little choice. The only move to protect a mate would be Qf5 or Qg5. Both of which is countered by g4.

Experiments with Neodymium magnets

I bought a set of neodymium to play with. When you are bored, without a computer, they come in handy.

The set consisted of 216 small 4-5mm balls of magnets. The magnets came in a 6x6x6 shaped cube. That shape was very unstable and stuck to the metallic box. On trying to break apart the cube the cube disintegrated into chains.

Trying to put back the magnets into a cube is not very easy. I can say that, because my friend, a physicist, also failed at the first attempt. Here's my approach and the difficulty I face along with the tricks involved.

My approach was to create a stack of 6 rings of the spheres each ring consisting of twelve balls.
Three stacks are required to make a cube. Here what the stacks looked like.

Now I flattened out all the stacks and formed sheets of 6x6x2,

Now I just stuck the stacks together and I had my cube.

The problem

The problem was to get a stack to align properly. Actually, there are two possible ways,

Proper (left) and improper (right) alignment

The one on the left is the desired one.

Proper (top) and improper (bottom) alignment

Also all the three stacks must align properly, although you don't have to combine those stacks. Because otherwise the 6x6x2 sheets would not stick together to form a cube. One of the sheets would slide over the other similar to the bottom chains in the above figure.

The trick

Suppose you are trying to join two stacks of rings and just would not align properly. The trick is to flip one stack and then try again. There's a catch here. If both of the stacks consist of even number of rings, flipping won't work. So adding rings one by one to a stack always works.

Suppose now you have formed three stacks of rings, all properly aligned. But all the three stacks do not align properly and so you cannot stick the respective sheets together. Here, atleast two stacks must be aligning properly and the third one would not align with any of the other two. So instead of  trying to re-create the third stack ad hoc, if all the rings of the third stack are inverted, it works. 

Here's the underlying diagrams.

Magnets aligning to form rings

The spheres colored regions inside the spheres represent the north and south poles of the magnet. So if two different configurations are superimposed they align properly, otherwise flipping one of them works. 

But suppose instead of a ring we have stacks of even number of rings ( both aligned properly ), flipping does not change the configurations of the stack and hence they will always align wrong. So inverting a ring, as follows, is required.

Inverting a ring (or stack of rings)

Here are some more configurations. Interestingly, the hexagon is more stable than the cube.