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

In article <1159436060.832981.92810@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
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.

But these examples are in some sense 'trivial'; I think that your
claim is true if these trivial examples are excluded. But I can't
at the moment work out a sufficiently general definition of 'trivial' ...


Mike Guy
.