Re: Can anyone provide some clues on how to prove a conjecture?

I wrote:
hooklee <hooklee@xxxxxxxxx> wrote:

Assume that $F(x)=F_{2m+1}\circ...\circ F_1(x)$ is a composition
function defined over {0,...,255}, where $F_{2i}(x)=x XOR a_i$ for
i=1~m, $F_{2i+1}(x)=(x+b_i) mod 256$ for i=1~(m+1), and a_i,
b_i\in{0,...,255}. If there exists c\in{0,...,255} such that $F(x)=x
XOR c$ holds for any x\in{0,...,255}, then c must be one of the
following two values: $c_1=XOR_{i=1}^m a_i$, or $c_2=c_1 XOR
128=(XOR_{i=1}^m a_i) XOR 128$. (XOR means bitwise exclusive OR.)

That certainly isn't true as it stands - for example take all the
b_i = 0. Then c can have an arbitrary value. A more complicated
example: take all the b_i to be multiples of 4, with Sum(b_i) = 0 (mod 256),
and all the a_i < 4.

Oops. I didn't read the question carefully. That isn't a
counterexample. The conjecture is in fact true unconditionally.

For convenience, replace F(x) by F(x) XOR a, where a = XOR_{i=1}^m a_i}.
Then the statement is: if F(x) = c XOR x then c = 0 or 128.

Each of the functions F_i defines a permutation of 0..255. So we rephrase
in terms of permutations.

In what follows, interpret addition modulo 256.

Let G be the group generated by the permutations b: x -> x+1 and
a_i: x -> x XOR i for 0<=i<=127. (Note we don't need a_i for i >= 128,
since a_{i+128} = b^128 a_i.)
Let c_i = a_i b a_i (0<=i<=127), and H be the subgroup of G generated
by the c_i. Then any permutation of the (modified) form F(x) lies in H,
since it can be written as
c_0^b_1 c_{a_1}^b_2 c_{a_1 XOR a_2}^b_3 ... .

So the required theorem is: a_i is in H <=> i = 0.

For i in 0..127, define d_i in H by
d_0 = c_0
d_{2^n+i} = c_{2^n-1-i} c_i for n in 0..6 and i in 0..2^n-1.

The d_i can be written explicitly as
d_0: x -> x+1
d_{2^n+i}: x -> x+2^(n+1) if x = i (mod 2^n) and x fixed otherwise.

Then we have
d_0^2 = d_1
d_{2^n+i}^2 = d^{2*2^n+i} d_{3*2^n+i} for n <= 5
d_{64+i}^2 = 0

The d_i generate H. Let H_i be the subgroup of H generated by
d_j, j >= i (so that H_0 = H). Then d_i is not in H_{i+1}, but (d_i)^2 is.
So H_{i+1} has index 2 in H_i, and the group H has order 2^128.
Further, any element of H can be uniquely written as
d_p d_q d_r d_s ... with p > q > r > s > ...

From the explicit definitions for d_i, we see that for each n in 0..7 and
for each x there is a unique d_i which adds 2^n to x. Write this i as
i(n, x). Note that i(n, x+2^(n-1)) = i(n, x).

If F(x) is expressible as a product of d_i, d_{i(n,x)} is in the product
exactly if the 2^n bit is present in the binary expansion of F(x) - x.

If F(x) is a_i with 2^(n-1) <= i < 2^n, F(0) - 0 = i and F(2^(n-1)) = i - 2^n.
So i(n, 0) is in the set of d_i, but i(n, 2^(n-1)) is not, giving a
contradiction.


Mike Guy
.

Relevant Pages