The following problem is related to (and motivated by) the first open case of [this MO question](https://mathoverflow.net/questions/148466/is-there-a-finite-family-of-functions-such-that-the-max-of-any-two-functions-can#comment382699_148466). It is difficult to believe that this is a hard problem; and yet, I do not have a solution.


For two vectors $x,y\in {\mathbb R}^4$, let us say that $x$ is *dominated* by $y$ if there are (at least) two coordinates in which $x$ is strictly smaller than $y$. With this convention, the problem goes as follows:



> 
> Does there exist a finite, non-empty set $S\subset {\mathbb R}^4$ with the property that for any two vectors $x,y\in S$, there exists yet another vector $z\in S$ such that the coordinate-wise maximum of $x$ and $y$ is dominated by $z$?
> 
> 
> 


Notice that it is easy to find a set of vectors with the property in question in ${\mathbb R}^5$ (see comments below), or to find a finite, non-empty set of vectors in ${\mathbb R}^4$ such that any vector is dominated by another one. On the other hand, there is no finite, non-empty set in ${\mathbb R}^4$ in which for any two vectors there is a third one exceeding their maximum in at least *three* coordinates.




---


*Post-factum: make sure you have not missed the extremely clever solution by zeb! It is not easy to follow, but I made an effort to trace it carefully and, as far as I can see, it is perfectly correct. Already the first step is very unusual: instead of looking at the smallest counterexample, zeb considers a counterexample which is by no means smallest, but instead has a comprehensible structure. Whether you have voted for the problem itself or not, consider voting for zeb's solution!*



"Circular" domination in ${\mathbb R}^4$
There is no such set $S$. Suppose for a contradiction that there was. By rescaling the coordinates, we can assume all coefficients of points in $S$ are positive integers. Now construct a set $S'$ as follows: for every point $(a,b,c,d)\in S$, put points $(a,b,0,0), (a,0,c,0), (a,0,0,d), (0,b,c,0), (0,b,0,d), (0,0,c,d)$ into $S'$. $S'$ will then be a solution to the problem if $S$ was, so replace $S$ by $S'$.


By adding finitely many additional points to $S$, we may further assume that if we decrease a coefficient of a point in $S$ by $1$, then the resulting point is still in $S$ as long as the coefficient was greater than $1$ to start with. $S$ now has the following properties:


**Property 0:** Every point in $S$ has exactly two positive coefficients, and the maximal $M$ such that $(M,1,0,0)\in S$ is the same as the maximal $M'$ such that $(M',0,1,0)\in S$.


**Property 1:** If $(a,b,0,0)\in S$ and $(0,0,c,d)\in S$, then at least one of $(a+1,0,c+1,0), (a+1,0,0,d+1), (0,b+1,c+1,0), (0,b+1,0,d+1)$ is in $S$.


**Proof:** Let $A$ be maximal such that $(A,b,0,0)\in S$ and let $D$ be maximal such that $(0,0,c,D)\in S$. Some element of $S$ dominates $(A,b,c,D)$, and by the choice of $A$ (respectively $D$) it can't have its last two (respectively first two) coefficients both equal to $0$.


**Property 2:** If $(x,y,0,0)\in S$, then at least one of $(x+1,0,0,2), (0,y+1,0,2)$ is in $S$.


**Proof:** Let $X$ be maximal such that $(X,y,0,0)\in S$, and let $M$ be maximal such that $(0,0,M,1)\in S$. Then some element $(a,b,c,d)$ of $S$ dominates $(X,y,M,1)$. By Property 0 we have $c\le M$, so $c = 0$. Since we can't have $(X+1,y+1,0,0)\in S$, $d$ must not be $0$, so $d \ge 2$ and either $a \ge X+1 \ge x+1$ or $b \ge y+1$.


Now consider the following property, depending on a parameter $k$:


**Property $k$:** If $(x,y,0,0)\in S$, then at least one of $(x+1,0,0,k), (0,y+1,0,k)$ is in $S$.


If $S$ has Property $k$ for every integer $k$, then clearly $S$ must be infinite. We'll now prove that in fact Property $k$ implies Property $k+1$ for $k \ge 2$, and this will give our desired contradiction.


**Property $k$ implies Property $k+1$:** Choose $A,B,C$ maximal such that $(A,0,0,k), (0,B,0,k), (0,0,C,k) \in S$. To see that such $A,B,C$ exist at all, we apply Property $k$ to the point $(1,1,0,0)$ to see that either $(2,0,0,k)$ or $(0,2,0,k)$ is in $S$, and then we apply Property $0$ to see that all of $(1,0,0,k), (0,1,0,k), (0,0,1,k)$ are in $S$.


Now we construct a sequence of points $s\_i \in S$, each with fourth coordinate equal to zero, as follows. Start with $s\_0 = (x,y,0,0)$. For each $i$, split into several cases:


1. If $s\_i = (0,u,v,0)$, apply Property 1 to $(0,u,v,0)$ and $(A,0,0,k)$, and call the resulting dominating point $s\_{i+1}$. If the fourth coordinate of $s\_{i+1}$ is nonzero, stop here.
2. If $s\_i = (u,0,v,0)$, apply Property 1 to $(u,0,v,0)$ and $(0,B,0,k)$. Proceed similarly to the above.
3. If $s\_i = (u,v,0,0)$, apply Property 1 to $(u,v,0,0)$ and $(0,0,C,k)$. Proceed similarly to the above.


The claim is that this process must stop, and the final $s\_{i+1}$ produced will be the point we are looking for. To see this, first note that we can never end up in the same case twice in a row during this process. Furthermore, we can never pass through all three cases in the course of this process: for instance, if we were to start in case 3 at step $i-2$, then go through case 2 at step $i-1$, and then end up in case 1 at step $i$, then if we write $s\_i = (0,u,v,0)$ we find that $u = B+1$ and $v = C+2$. Applying Property $k$ to $s\_i$, we see that one of $(0,B+2,0,k), (0,0,C+3,k)$ is in $S$, contradicting the choice of $A,B,C$.


Thus, the process alternates between case 3 and some other case, say case 2 for concreteness. At each step, the first coordinate of $s\_i$ will then increase, and inductively we see that for $i\ge 0$, the first coordinate of $s\_i$ is $x+i$. Since it can't increase without bound, the process must eventually end. If it ends after step $0$, then the dominating vector $s\_1$ is either $(x+1,0,0,k+1)$ or $(0,y+1,0,k+1)$. If it ends after step $i$ for $i\ge 1$, then the dominating vector $s\_{i+1}$ must be $(x+i+1,0,0,k+1)$, since otherwise it would be either $(0,B+2,0,k+1)$ or $(0,0,C+2,k+1)$ depending on whether $i$ was even or odd, contradicting the choice of $A,B,C$.


