We prove that for all positive integer $k$ and for all
sufficiently small $\epsilon >0$ if $n$ is sufficiently large
then there is no Boolean (or $2$-way) branching program of size
less than $2^{\epsilon n}$ which for all inputs
$X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$
the parity of the number of elements of the set of all pairs
$\langle x,y\rangle $ with the property $x\in X$, $y\in X $,
$x<y$, $x+y\in X$. For the proof of this fact we show that if
$A=(a_{i,j})_{i=0,j=0}^{n}$ is a random $n$ by $n$ matrix over
the field with $2$ elements with the condition that
``$\forall i,j,k,l\in \lbrace 0,1,...,n-1\rbrace $, $i+j=k+l$
implies $a_{i,j}=a_{k,l}$" then with a high probability the rank
of each $\delta n$ by $\delta n$ submatrix of $A$ is at least
$c\delta |\log \delta |^{-2}n$, where $c>0$ is an absolute
constant and $n$ is sufficiently large with respect to $\delta$.