8
$\begingroup$

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.

  • 2
    @Carl: And even a non-tilted square may have just one integral vertex.2012-11-08

3 Answers 3

0

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.

  • 0
    @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 :(2012-11-08
3

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.

3

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.

  • 0
    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.2012-11-08