| First, note that the value of a symmetric boolean function is simply a
function of the sum of its arguments -- that is, the number of bits set.
Thus, we can describe the symmetric function f: {0,1}^n -> {0,1} by the
boolean vector b[0..n], of n+1 elements, which gives the value of f when
indexed by the count of the non-zero arguments to f.
For the function to be 1-resilient, we can consider all possible outcomes
of the (remaining) random flips, and verify that just half of these produce
a zero. Letting c(n,k) be the number of combinations of {0,1}^n that have
exactly k bits set, the function is 1-resilient if and only if:
n-1 n-1
Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i), and
i=0 i=0
n n
Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i).
i=1 i=1
Note that c(n,k) is simply a binomial coefficient (n choose k), so the above
equations are:
n-1 n-1
Sum b[i]*c(n-1,i) = 2 , and
i=0
n n-1
Sum b[i]*c(n-1,i) = 2 .
i=1
This gives us a convenient way to test a function for 1-resiliency.
[ The corresponding set of equations required for t-resiliency are:
n-t+k n-t
Sum b[i]*c(n-t,i) = 2 , 0 <= k <= t. ]
i=k
The question is whether there are any solutions (the vector b) to the
equations for 1-resiliency, besides: b[i] = odd(i), and b[i] = not odd(i).
[ Posed another way, the question of 1-resiliency is similar to asking whether
the multi-set of binomial coefficients {c(n,0), c(n,1), ..., c(n,n)} can be
divided into two subsets having equal sums, in two different ways. ]
If n-1 is a prime, it's simple to show that b[n] = not b[0], since the binomial
coefficients for all the other terms are multiples of n-1, and these two terms
must 'cancel' for the sums to work out right.
|
| Re .1:
It's early in the morning, so I may be missing something, but:
> n n
> Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i).
> i=1 i=1
When i=n, I take it c(n-1,n) should be zero? But then the expression on
the right is equal to 1/2 (2^(n-1)-1).
> n-1 n-1
> Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i), and
> i=0 i=0
Note that the expression on the right here is 1/2 (2^(n-1)) or 2^(n-2).
> n-1 n-1
> Sum b[i]*c(n-1,i) = 2 , and
> i=0
So this is wrong; it should be 2^(n-2).
> n n-1
> Sum b[i]*c(n-1,i) = 2 .
> i=1
And this should be 1/2 (2^(n-1)-1).
-- edp
|
| [ The following corrects some minor errors that were in 371.2 ]
First, note that the value of a symmetric boolean function is simply a
function of the sum of its arguments -- that is, the number of bits set.
Thus, we can describe the symmetric function f: {0,1}^n -> {0,1} by the
boolean vector b[0..n], of n+1 elements, which gives the value of f when
indexed by the count of the non-zero arguments to f.
For the function to be 1-resilient, we can consider all possible outcomes
of the (remaining) random flips, and verify that just half of these produce
a zero. Letting c(n,k) be the number of combinations of {0,1}^n that have
exactly k bits set, the function is 1-resilient if and only if:
n-1 n-1
Sum b[i]*c(n-1,i) = (1/2) Sum c(n-1,i), and
i=0 i=0
n n
Sum b[i]*c(n-1,i-1) = (1/2) Sum c(n-1,i-1).
i=1 i=1
Note that c(n,k) is simply a binomial coefficient (n choose k), so the above
equations are:
n-1 n-2
Sum b[i]*c(n-1,i) = 2 , and
i=0
n n-2
Sum b[i]*c(n-1,i-1) = 2 .
i=1
This gives us a convenient way to test a function for 1-resiliency.
[ The corresponding set of equations required for t-resiliency are:
n-t n-1-t
Sum b[i+k]*c(n-t,i) = 2 , 0 <= k <= t. ]
i=0
The question is whether there are any solutions (the vector b) to the
equations for 1-resiliency, besides: b[i] = odd(i), and b[i] = not odd(i).
[ Posed another way, the question of 1-resiliency is similar to asking whether
the multi-set of binomial coefficients {c(n,0), c(n,1), ..., c(n,n)} can be
divided into two subsets having equal sums, in two different ways. ]
If n-1 is prime, it's simple to show that b[n-1] = not b[0], since the binomial
coefficients for all the other terms are multiples of n-1, and these two terms
must 'cancel' for the sums to work out right.
- Gilbert
|
| I've found two counter-examples.
Let f be a function from {0,1}^14 to {0,1}, such that f is 1 iff the number
of 1s in its arguments is in the set {1,3,4,7,8,11,13}. The relevant line
from Pascal's triangle is:
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
13 +286+715 +1716+1287 +78 +1 = 2^12
1 +78+286 +1716+1716 +286 +13 = 2^12
Let f be a function from {0,1}^15 to {0,1}, such that f is 1 iff the number
of 1s in its arguments is in the set {0,2,3,6,7,10,12,14}. The relevant line
from Pascal's triangle is:
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 +91 +1001+2002 +3003+2002 +91 +1 = 2^13
14 +364+1001 +3432+3003 +364 +14 = 2^13
These solutions (and their reflections) are the only non-XOR 1-resilient
symmetric functions of 28 or fewer variables.
I haven't checked whether either of these can be used to get 2-resiliency.
- Gilbert
|