Simple-looking number theory or combinatorics problem

[larryh...@telus.net]

Let p be an odd number and write P for the ring of residue classes of
integers mod p. Let f and g be two mappings of P into the set {0,1}.
Show that if sum_(i \in P) f(i) g(x-i) is an even number for all x in
P, then f or g is constant.

I can do it with a bit of slightly advanced algebra, but a dirt-simple
demonstration would be nice.

[billh04]

On Aug 16, 9:03 am, "larryhamm...@telus.net" <larryhamm...@telus.net>
wrote:

Not sure about the following.

Without loss of generality (WLOG), we can assume that f(i) = 1 for 0
<= i <= m else 0.
Note that interchanging j and k for f corresponds to interchanging -j
and -k for g.

If f equals 0 for all i (ie, m = -1), then there is nothing to prove.
Hence, m >= 0.

If f equals 1 for all i (ie, m = p -1), then there is nothing to
prove. Hence, m < p -1.

If m = 0, then g is the constant function 0. Hence, 0 < m < p - 1.

Each sum now looks like:

g(x-0) + g(x-1) + ... g(x-m - 1) is even.

Add the first and second, second and third, third and fourth, etc. We
get:

g(0) = g(m)
g(1) = g(m+1)
g(2) = g(m+2)
....

It follows that g is a constant function.

The details require some work. I didn't check, so the above may not
work.

Bill Hale

[larryh...@telus.net]

On Aug 16, 11:46 pm, billh04 <h...@tulane.edu> wrote:
> Not sure about the following.
>
> Without loss of generality (WLOG), we can assume that f(i) = 1 for 0
> <= i <= m else 0.
> Note that interchanging j and k for f corresponds to interchanging -j
> and -k for g.
>
> If f equals 0 for all i (ie, m = -1), then there is nothing to prove.
> Hence, m >= 0.
>
> If f equals 1 for all i (ie, m = p -1), then there is nothing to
> prove. Hence, m < p -1.
>
> If m = 0, then g is the constant function 0. Hence, 0 < m < p - 1.
>
> Each sum now looks like:
>
>      g(x-0) + g(x-1) + ... g(x-m - 1) is even.
>
> Add the first and second, second and third, third and fourth, etc. We
> get:
>
>    g(0) = g(m)
>    g(1) = g(m+1)
>    g(2) = g(m+2)
>       ....
>
> It follows that g is a constant function.
>
> The details require some work. I didn't check, so the above may not
> work.
>
> Bill Hale

Something more is needed, because the statement fails if p is even,
e.g. p=6 and the matrix [ f(m) g(n) ] is:

0 1 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0

But I think I can push it through by just permuting two consecutive
columns of the matrix and studying what happens to the count of 1's
along the "diagonals" (of which there are p; it's like a p-by-p
torus).

Thanks Bill.

[Larry Hammick]

On Aug 16, 7:03 am, "larryhamm...@telus.net" <larryhamm...@telus.net>
wrote:

> Let p be an odd number and write P for the ring of residue classes of
> integers mod p. Let f and g be two mappings of P into the set {0,1}.
> Show that if sum_(i \in P) f(i) g(x-i) is an even number for all x in
> P, then f or g is constant.

Er, that's not quite true. Here's a matrix [ f(x) g(y) ] for which it
fails:

1 1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0
1 1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

So I'll add a restrictive hypothesis:
The function x\mapsto f(x) and x\mapsto f(x+k) are distinct unless k
is 0 mod p.

[Tonico]

On Aug 17, 8:06 pm, "larryhamm...@telus.net" <larryhamm...@telus.net>
wrote:

You stated p is odd...

Tonio

[Larry Hammick]

Yes I know, but I meant, the inductive argument sketched by Bill Hale
(if I'm reading it right) would apply to even p as well as odd. So I
think there must be something wrong with that argument.
LH

[Larry Hammick]

> Er, that's not quite true. Here's a matrix [ f(x) g(y) ] for which it
> fails:
>
> 1 1 0 1 1 0 1 1 0
> 1 1 0 1 1 0 1 1 0
> 1 1 0 1 1 0 1 1 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
> 0 0 0 0 0 0 0 0 0
>
> So I'll add a restrictive hypothesis:
> The function x\mapsto f(x) and x\mapsto f(x+k) are distinct unless k
> is 0 mod p.

Hell, even that isn't true. E.g.
0 0 1 0 1 1 1
0 0 1 0 1 1 1

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

0 0 1 0 1 1 1

0 0 0 0 0 0 0

sum_(i \in P) f(i) g(x-i) is an even number for all x. Yuck.