"Circular" domination in ${\mathbb R}^4$

Question

The following problem is related to (and motivated by) the first open case of this MO question. 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!

Answer 1

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$.

Answer 2

This may be a start. Assuming there exists such a finite $S$, we can apply the extremal principle in several ways to get constraints.

Notation : For distinct $x,y\in S$, we’ll denote by $x\cup y$ the vector of their coordinate-wise maxima and refer to it as a pair. Further denote $I := \lbrace 1,2,3,4\rbrace$.

Assume that $S$ has minimal size. Then each $x\in S$ is needed to dominate some pair.

Within each coordinate $i$, label the occurring entries from smallest ($0$) to biggest (call that $m_i$). We can wlog replace the entries of all vectors of $S$ by these labels. Note that each number of $\lbrace 0,\dots,m_i\rbrace$ occurs as $i$th coordinate for some vector in $S$.

We will now try to « compress » a coordinate. By this I mean that we choose an $i\in I$ and for each $x\in S$ such that $x_i\ne0$, replace $x_i$ by $x_i-1$. As long as the modified set still satisfies the property, we can iterate this process and will eventually come to a contradiction, as all coordinates will end up as $0$ everywhere. So (as we have assumed the existence of an initial S), the property must be violated at one of these iterations, and this will yield us some constraints.

Compress the first coordinate as long as it works, then the 2nd, 3rd, 4th.

The property will be violated for the first coordinate iff there are $a^1,b^1\in S$ with $a^1_1=b^1_1=0$ such that each vector $x\in S$ that dominates $u^1:=a^1\cup b^1$ has $x_1=1$. (This is because if there is always such an $x$ with $x_1>1$ or $x_1=0$, the compression does not interfere with the property). Otherwise stated, each $x\in S$ with $x_1>1$ must have $x_i\le u^1_i$ for $i=2,3,4$. $(*)$. Similarly for the other coordinates.

For each $i\in I$ take a vector $v^i\in S$ such that its $i$th coordinate $v^i_i=m_i$ is maximal. It is easy to see that $v^1,\dots,v^4$ must be all distinct, i.e. no vector of $S$ can be maximal in more than one coordinate. $(**)$

Suppose $v^i_j>1$ for a $j\ne i$. Then by $(*)$, we must have $m_i=v^i_i\le u^j_i$, thus $u^j_i=m_i$ because this is maximal.

Each of $a^j$ and $b^j$ can only have one coordinate maximal because of $(**)$. As $u^j=a^j\cup b^j$, for each $i$ there is at least one $j\ne i$ such that $v^i_j\le1$.

So we know that each vector $v^i$ as above (i.e. with a maximal $i$th coordinate) must have another coordinate $\le 1$.

I don't know if that will help a lot for carrying on. It also seems (but my proof of that is not yet complete) that there must be a (unique?) $w\in S$ that dominates all pairs $v^i\cup v^j$, and from there it might be possible to go quite far towards the so eagerly searched contradiction.

Answer 3

This is only little more than a comment.

By $t \to -t$ the question of circular domination is equivalent to finding a set where the coordinate wise minimum of each pair $x,y$ dominates $z$ in $S$, or $z <_2 \min(x,y)$.

Assume there is a finite $S=\{s_0,\ldots,s_n\} $ with a minimal number $n+1$ of elements, such that each set with fewer elements, does not have circular domination. Then for each coordinate $i=1,\ldots,4$ it is possible to replace the real numbers $S=\{s_{0,i},\ldots,s_{n,i}\} $
by the natural numbers $\{0,1,\ldots,n\}$ while retaining the order. If some real coordinates are equal, one can choose any order of the corresponding natural numbers without destroying circular domination. (e.g. replace $(-0.3, -0.1, 0, 0, 0, 0.3, 1.5)$ with $(0,1,2,3,4,5,6)$ or $(0,1,4,2,3,5,6)$ )

Proof: For $u,v,w \in S$ with $u <_2 \min(v,w)$ then also for the renumbered set we have $nat(u) <_2 \min(nat(v), nat(w))$.

Therefore, if any minimal set $S$ exists, one can find a minimal set $S$ where the $i$-th coordinates are permutations of $\{0,1,\ldots,n\}$. This shows that the problem of deciding whether circular domination is possible in a set with $k$ elements is a finite problem. By brute force computing I could at least show that circular domination requires $k>6$.

This formulation also helps to see that in each coordinate there are

$n$ pairs which have minimum 0,

$n-1$ with minimum 1

and so on. The expected value of each coordinate minimum of two elements is $\frac{ n+2}{3}$. This substantiates the intuition that there are not enough small numbers, such that each of the elements is dominated by a minimum of two others. However, this must be the case in a minimal circular set (otherwise just throw away the elements which are not, and you still have a circular set). I couldn't transform this into a proof, though.

Answer 4

Take $S_N=\left \{x_n\right \}_{n=1}^N$ where $x_n=(n,n,1/n,1/n)$. Then $$\max\left \{x_n,x_m \right \}=(\max\left \{n,m \right \},\max \left \{n,m \right \},1/\min\left \{n,m \right \},1/\min \left \{n,m \right \}).$$ If $n<N$ and $m<N$, then $\max\left \{x_n,x_m \right \}$ is dominated by $x_N$. If $n>1$ and $m>1$, then $\max\left \{x_n,x_m \right \}$ is dominated by $x_1$. Also $\max\left \{x_1,x_N \right \}$ is dominated by $x_n$ for any $n\neq1$ or $N$.