Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A problem in the 2009 Putnam asks about functions $f:\mathbb{R}^2 \to \mathbb{R}$ such that whenever $A,B,C,D$ are corners of some square we have $f(A)+f(B)+f(C)+f(D)=0$. Without spoiling the problem too much, I'll just mention that my solution breaks down if we change the range of the function to be, say, a field of characteristic 2.

So, what if we take the range to be the field of two elements? Are there non-constant functions with this property taking values in $\mathbb{Z}/2\mathbb{Z}$?

I'm guessing the answer is No, but I don't have proof. It seems to me that nothing analogous to the fairly simple approach I took in the original problem would work here. I've ruled out various simple constructions and various simple obstructions but haven't made much more progress.

share|improve this question
    
1 when both coordinates are integers? –  Carl Nov 8 '12 at 8:57
    
Note (just for fun) that $f: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$ with any square's corners summing to zero implies that $f$ must be $0$ everywhere. Question: if we define $g: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}/2\mathbb{Z}$ by $g(m, n) := mn$ mod $2$, do we end up with a non-constant function with this property? –  Benjamin Dickman Nov 8 '12 at 9:11
    
@Carl: no. A tilted square may have just one integral vertex. –  Alon Amit Nov 8 '12 at 9:14
1  
@Carl: And even a non-tilted square may have just one integral vertex. –  Marc van Leeuwen Nov 8 '12 at 11:06

3 Answers 3

up vote 3 down vote accepted

Let a square be subdivided into four subsquares, and label the points by their values mod 2 under the map from $R^2$ to $Z_2$. Let the vertices of the "big square" be $a,c,g,i$. The upper left subsquare has vertices $a,b,d,e$, The upper right square has vertices $b,c,f,e$, the lower left subsquare has vertices $d,e,h,g$, and the lower right square has vertices $e,f,i,h$. There is also the "diagonal square" with vertices $b,f,h,d$. Thus the point labelled $e$ is at the center of the big square, and the vertices of the diagonal square are at the midpoints of the sides of the big square.

Now the assumptions are that the sum of the vertices of each square (recall by the labellings I mean the value in $Z_2$ assigned to the given vertex) is zero mod 2. Now consider the algebraic identity $$2d+g+2h -(d+e+g+h)+(b+c+e+f)-(b+d+f+h)=c.$$ The terms here in parentheses are $0$ mod 2 by assumption, since they are respectively the vertices of the lower left, upper right, and diagonal subsquares. And mod 2 the left side is $g$. So what we have is that $g=c$ mod 2.

Our conclusion is that, under the mapping, every square has the same value mod 2 assigned to each pair of diametricdally opposite vertices.

We can use this to show the map is constant mod 2 on the plane: Let say $k$ be the value mod 2 assigned to the origin $(0,0)$. Let $P=(x,y)$ be any point other than the origin. There is then a square having diametrically opposite vertices, one at $(0,0)$ and the other at $(x,y)$. By what we have shown above, the values mod 2 of the map at (0,0) and at $(x,y)$ must be the same, so that the map at $(x,y)$ must be $k$ as well. So the map is constant mod 2.

share|improve this answer
    
Right - a bit more simply, the three squares d+e+g+h, b+c+e+f and b+d+f+h add up to 0 and adding these up yields c+g=0. Since any two arbitrary points can take the roles of c and g, we're done. Thanks! –  Alon Amit Nov 8 '12 at 18:38
    
I didn't notice the simple case of the three squares you use here; what I did was basically to "solve the system" (putting arbitrary letters on the right side of each of the five sums), and look for one which gave a nontrivial relation mod 2 on the $a,..,i$. In fact this is the approach some of us used on the Putnam problem, while discussing it for some students who were to take the test. –  coffeemath Nov 8 '12 at 23:22

Given a value for $f(0,0), f(0,1), f(0,2)$, and $f(1,1)$, using your relationship on squares on side length $1$ and $\sqrt 2$, you deduce the value of $f$ on $\mathbb Z^2$.

Given there are $16$ possible choices for the values of $f$ on this four points, this give the $16$ solutions on $\mathbb Z^2$ : There are $4$ families :

  • the two constant functions ($f(x,y) = 0$, ...)
  • the two chessboards ($f(x,y) = x+y \pmod 2$, ...)
  • the eight "size 2" chessboards ($f(x,y) = [x/2]+[y/2] \pmod 2$, ...)
  • the four "alternating lines" functions ($f(x) = x \mod 2$, ...)

You will notice that $f(0,0) = f(4,0)$ in every case.

Thus if you have a non constant coloring, find two points of different color, label them $(0,0)$ and $(4,0)$, then you will not be able to define $f$ on the lattice induced by your two points.


Actually, this works with functions having values in any finite commutative group $G$. The condition on squares on size $1$ and $\sqrt 2$ give a transfer automorphism $T : G^4 \to G^4$ mapping $(f(0,0),f(0,1),f(0,2),f(1,1))$ to $(f(1,0),f(1,1),f(1,2),f(2,1))$. Since $G$ is finite, there is a period $n$ such that $T^{\circ n} = id$, which means that any solution on $\mathbb Z^2$ is $n$-periodic (in both directions). So you just pick two points with distinct values by f and draw the appropriate lattice where they are $n$ units apart to get a contradiction.

share|improve this answer

I'm not sure I understand your mentioned solution of the original question: how can a function $f: \mathbb{R}^2\rightarrow \mathbb{R} $ have as range $\mathbb{Z}/{2\mathbb{Z}}$?

Anyway, here's a non-constant function with your desired range (EDIT: works only on square parallel to x,y axis):

$$f: \mathbb{R}^2\rightarrow \mathbb{Z}/{2\mathbb{Z}}$$ $$ f(x,y) = \begin{cases} 1 &\mbox{if } x \in \mathbb{Q} \\ 0 & \mbox{if } x \notin \mathbb{Q} \end{cases} $$

To check that is satifies the required properties, take a square ABCD with coordinates $A=(x_1,y_1),B=(x_1,y_2),C=(x_2,y_2),D=(x_2,y_1)$ It's obvious that f(A) = f(B) and f(C)=f(D), and hence the sum becomes zero for any choice of A, B, C, and D.

This works also for any rectangles.

share|improve this answer
    
Unfortunately, I never said that the square has to have sides parallel to the axes of the plane. Thus $A=(0,0), B=(\sqrt{5},\sqrt{5}), C=(2\sqrt{5},0), D=(\sqrt{5},-\sqrt{5})$ is a square for which the proposed function sums to 1. My original solution works perfect for the case $f:\mathbb{R}^2\to\mathbb{R}$; my point was that it stops working if we change the range from $\mathbb{R}$ to Z/2Z. Hence my question. –  Alon Amit Nov 8 '12 at 8:16
    
Ok, i'm stuck for now. I figured that using the fact that the sum of two rationals is still a rational might have been enough. Apparently not :( –  Sir.Rainbow Nov 8 '12 at 9:04
    
I have another idea but it's been a while since I've used any Algebra, maybe it is useful to someone: look at the set of functions S that satisfy the property: It is a group with respect to +, with the 0 function as 0 element. Now consider all transformation of the plane that don't destroy squares (like rotations, expansions, etc...) This acts on S by precomposition: maybe you can use this to show that S is the trivial group and hence no such function exists. –  Sir.Rainbow Nov 8 '12 at 9:09
    
@Sir.Rainbow: For achieving what you did for non-tilted rectangles, you could use any non-constant function $\Bbb R\to\Bbb Z/2\Bbb Z$ of the $x$ coordinate in the place of the characteristic function of $\Bbb Q$. For instance $x\mapsto\lfloor x\rfloor\bmod 2$ would do fine. –  Marc van Leeuwen Nov 8 '12 at 12:27
    
@MarcvanLeeuwen yeah I know, but I didn't start out with the non-tilted requirement in mind, it crept in by the way I drew the square on paper :( –  Sir.Rainbow Nov 8 '12 at 13:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.