34
$\begingroup$

Setup

Let $A=\{a_1<a_2<\cdots<a_p\}$ and $B=\{b_1<b_2<\cdots<b_q\}$ be two finite sets of real numbers. Define an equivalence relation $\sim_{A,B}$ on $R_{p,q}=\{1,\dots,p\}\times\{1,\dots,q\}$ by setting $$(i,j)\sim_{A,B}(k,l)\iff a_i+b_j=a_k+b_l$$ and further define a total order on the set of equivalence classes $R_{p,q}/\sim_{A,B}$ by setting, for any equivalence classes $c,d$ and representatives $(i,j)\in c$ and $(k,l)\in d$ $$c<_{A,B}d\iff a_i+b_j<a_k+b_l$$ This question is about characterizing such equivalence relations $\sim_{A,B}$ and total orders $<_{A,B}$. An equivalence relation $\sim$ on $R_{p,q}$ for which there exist $A,B$ with $\sim\;=\;\sim_{A,B}$ is called realizable. If $\sim$ is realizable, a total order $<$ on $R_{p,q}/\sim$ is called realizable if we can find $A,B$ with $\sim\;=\;\sim_{A,B}$ and $<\;=\;<_{A,B}$. In both cases we say that the pair $(A,B)$ realizes $\sim$ (resp. $(\sim,<)$.)

Problem 1. Characterize realizable equivalence relations on $R_{p,q}$.

Problem 2. Suppose $\sim$ is realizable, can one find $\mathcal{A},\mathcal{B}\subset\Bbb{N}$ with $\sim\;=\;\sim_{\mathcal{A}, \mathcal{B}}$?

Problem 3. Characterize realizable orders on $R_{p,q}/\sim$ (where $\sim$ is realizable.)

Have these questions been considered / solved somewhere?

Motivation

As suggested in the comments I should give some context. The question arose while solving Problem 3.5 in David Eisenbud's Commutative Algebra with a View Toward Algebraic Geometry. In this problem one considers a graded ring $R=\bigoplus_{\gamma\in\Gamma} R_\gamma$ and a graded module $M=\bigoplus_{\lambda\in\Lambda}M_\lambda$ where $(\Gamma,+,0,<)$ is a totally ordered abelian monoid acting freely and compatibly on the totally ordered set $(\Lambda,<)$. When working out the solution to this exercise I found myself drawing rectangles $R_{p,q}=\{1,\dots,p\}\times\{1,\dots,q\}$ and writing $\gamma_i+\lambda_j$ at position $(i,j)$, where I had picked some subsets $\{\gamma_1<\gamma_2<\cdots<\gamma_p\}\subset\Gamma$ and $\{\lambda_1<\lambda_2<\cdots<\lambda_q\}\subset\Lambda$. I was trying to figure out when $R_{\gamma_i}\cdot M_{\lambda_j}$ and $R_{\gamma_k}\cdot M_{\lambda_l}$ lie in the same $M_{\lambda}$ i.e. what and one say about the equivalence relation on $R_{p,q}$ defined by $(i,j)\sim(k,l)\iff\gamma_i+\lambda_j=\gamma_k+\lambda_l$? For concreteness I considered $\Gamma=\Lambda=\Bbb{N}$ or $\Gamma=\Lambda=\Bbb{R}_+$ but the problem makes sense in the broader context described by Eisenbud. I realized that there were some nice pictures to be drawn and that there was a not so obvious combinatorial problem of independent interest which is Problem 1. Problem 2 arose when comparing the cases $\Bbb{N}$ and $\Bbb{R}_+$: do we recover the same equivalence relations? Or would some not be realizable using integers? Problem 3 arose when drawing not only the blobs representing equivalence classes but the total order between them. What constraints must such orders satisfy?

Necessary conditions and proposed characterizations

While thinking about these problems I made some progress and was able to identify some necessary conditions for realizability of $\sim$ and $<$. I wouldn't call any of these "conjectures" per se ... Is there an acceptable phrase for "half-assed guesses"? Using terminology introduced below I wonder

Observation and Guess 1. Any realizable equivalence relation $\sim$ on $R_{p,q}$ satisfies Inclination, Non Crossing and both Antidiagonal Propagation conditions. Conversely, are these conditions enough to characterize realizability of $\sim$ ?

I'm not sure these conditions alone will do the job ... but they may. It seems in that for $p=2$ these conditions are sufficient (with an algorithm for finding explicit sets $A,B$ of rational numbers realizing $\sim$.)

Using terminology introduced below, there are some simple necessary Visibility conditions satisfies by realizable orders. There are also some less obvious but still simple Horizontal and Vertical Coherence conditions that such orders must satisfy.

Observation and Guess 2. Any realizable order satisfies Visibility and both Horizontal and Vertical Coherence conditions. Conversely, are these enough to characterize realizability of $<$ ?


Examples

Here are some simple examples representing equivalence classes of $\sim_{A,B}$ and the order relation $<_{A,B}$. In the pictures below we represent equivalence classes as "blobs" and signify $c<_{A,B}d$ by drawing an arrow from one equivalence class to another.

Example 1. Let $A=\{0<1<2<\cdots<p-1\}$ and $B=\{0<p<2p<\cdots<(q-1)p\}$. The equivalence classes of $\sim_{A,B}$ are singletons (this is uniqueness of euclidean division).

enter image description here

Example 2. Let $A=\{0<1<2<\cdots<p-1\}$ and $B=\{0<1<2<\cdots<q-1\}$. The equivalence classes of $\sim_{A,B}$ are antidiagonals.

enter image description here


The answer to Problem 2 may be positive. Something along the lines of "the condition is open and as long as one moves in tandem the things that are correlated (i.e. related by $\sim_{A,B}$) one can change coordinates to rational ones" ought to "prove" the assertion. Maybe results from real algebraic geometry and semi-rational sets of degree 1 could also answer the question, but I know nothing about this material. Once one has rational $A$ and $B$ one can multiply everything by some integer and get the desired integer $\mathcal{A}$ and $\mathcal{B}$.

There may be a connection with configuration spaces. There certainly is a connection with geometry (existence of rational points on a rational algebraic set) and hyperplane arrangements but there, too, I'm not quite sure how to make it precise.


Notation

Given an equivalence class $c$ for $\sim_{A,B}$ we define its sum to be $a_i+b_j$ for any $(i,j)\in c$. Given $(i,j)\in R_{p,q}$ we define the vertical set $V_i=\{(i,a)\mid a=1,\dots,q\}$ and the horizontal set $H_j=\{(a,j)\mid a=1,\dots,p\}$. Given an equivalence class $c$ we define two subsets of the rectangle: $c^+$ (the green shaded region in the picture below) is the set of all $(i,j)$ such that there exists some $(a,b)\in c$ with $(a,b)\neq(i,j)$ and $a\leq i$ and $b\leq j$ and $c^-$ (the orange shaded region in the picture below) is the set of all $(i,j)$ such that there exists some $(a,b)\in c$ with $(a,b)\neq(i,j)$ and $a\geq i$ and $b\geq j$. In the picture below the blue dots represent an equivalence class, the green region is $c^+$ and the orange region is $c^-$.

enter image description here


Inclination and Non Crossing (necessary conditions for realizability of $\sim$)

The following are simple necessary conditions on an equivalence relation $\sim$ on $R_{p,q}$ for it to be of the form $\sim_{A,B}$:

Inclination. Two equivalent elements may not have the same first or second coordinate, i.e. any intersection $c\cap V_i$ and $c\cap H_j$ contains at most one element.

Non Crossing. Given distinct equivalence classes $c,c'$, the equivalence class $c'$ may not intersect both $c^+$ and $c^-$.

The necessity of both conditions is clear (the sum of an equivalence class meeting $c^+$ (resp. $c^-$) is greater (resp. smaller) than that of $c$). Actually the first condition is redundant since it is contained in the second. These conditions alone, however, don't characterize equivalence classes of the form $\sim_{A,B}$, see the counter example below.

Constraints and counter example

Some configurations of equivalence classes have a constraining effect on the rest of the equivalence classes. Consider for example the case where we have an antidiagonal and subantidiagonal equivalence class (say with $p=q=n+1\geq 3$) i.e. $(1,n)\sim_{A,B}(2,n-1)\sim_{A,B}\cdots\sim_{A,B}(n,1)$ and $(1,n-1)\sim_{A,B}(2,n-2)\sim_{A,B}\cdots\sim_{A,B}(n-1,1)$. Then $(i,j)\sim_{A,B}(k,l)\iff i+j=k+l$.

enter image description here

This implies that some equivalence relations are not of the form $\sim_{A,B}$ even though they satisfy the Inclination and Non Crossing conditions. For example the one depicted below:

enter image description here

These can't represent the equivalence classes of a relation $\sim_{A,B}$: the presence of the $3$ element equivalence classes would impose the relations $(1,3)\sim_{A,B}(2,2)$ and $(2,7)\sim_{A,B}(3,6)$ (both represented in blue on the right).

We thus get a third necessary condition:

Suppose $A'=\{a_1',\dots,a_r'\}\subset A$ and $B'=\{b_1',\dots,b_r'\}\subset B$ for $r\geq 3$ satisfy either that $(1,r-1)\sim_{A',B'}(2,r-2)\sim_{A',B'}\cdots\sim_{A',B'}(r-1,1)$ and $(1,r-2)\sim_{A',B'}(2,r-3)\sim_{A',B'}\cdots\sim_{A',B'}(r-2,1)$ or the analoguous condition with the antidiagonal above the principal antidiaongal. Then for all $1\leq i,j,k,l\leq r$, $(i,j)\sim_{A',B'}(k,l)\iff i+j=k+l$.

It turns out we can improve on this condition.

Antidiagonal Propagation (necessary condition for realizability of $\sim$)

There are two versions of antidiagonal propagation: the one described below where we consider a main antidiagonal and one below it, but one should add the other possibility too, where the smaller antidiagonal is above the larger one.

Antidiagonal Propagation. Suppose $A=\{a_1<a_2<\cdots<a_n\}$, $B=\{b_1<b_2<\cdots<b_n\}$ with $n=mT+r$ with $m+1\geq 3$, $T\geq 1$, $\newcommand{\T}{[\![1,T]\!]}r\in\T$. Suppose $$\newcommand{\n}{[\![1,n]\!]} \forall i,j\in\n, \quad \begin{cases} i+j=n+1:& a_i+b_j=C\\ i+j=n+1-T:& a_i+b_j=D \end{cases}$$ Then $$\newcommand{\n}{[\![1,n]\!]} \forall i,j,k,l\in\n, \quad \left\{ \begin{array}{l} i\equiv k\mod T,\\ j\equiv l\,\mod T,\\ \text{and }i+j=k+l \end{array} \right\} \implies (i,j)\sim_{A,B}(k,l)$$

In other words if $(i,j)$ and $(k,l)$ lie on the same antidiagonal and are a multiple of $T$ positions apart then they are $\sim_{A,B}$-equivalent.

Proof. The condition implies that, setting $\Delta=C-D$, $$ \left\{ \begin{array}{lll} a_{1+kT}=a_1+k\Delta, & b_{1+kT}=b_1+k\Delta & ~\text{for }k=0,1,\dots,m-1,m\\ a_{2+kT}=a_2+k\Delta, & b_{2+kT}=b_2+k\Delta & ~\text{for }k=0,1,\dots,m-1,m\\ \qquad\vdots&\qquad\vdots&\qquad\vdots\\ a_{r+kT}=a_r+k\Delta, & b_{r+kT}=b_r+k\Delta & ~\text{for }k=0,1,\dots,m-1,m\\[2mm]\hline a_{r+1+kT}=a_{r+1}+k\Delta, & b_{r+1+kT}=b_{r+1}+k\Delta & ~\text{for }k=0,1,\dots,m-1\\ \qquad\vdots&\qquad\vdots&\qquad\vdots\\ a_{T+kT}=a_T+k\Delta, & b_{T+kT}=b_T+k\Delta & ~\text{for }k=0,1,\dots,m-1 \end{array} \right. $$ and thus if $i\equiv k\mod T$, say $i=IT+\tau$, $k=KT+\tau$, $j\equiv l\mod T$, say $j=JT+\sigma$, $l=LT+\sigma$, and $i+j=k+l$ i.e. $I+J=K+L$, then $$ a_i+b_j = a_\tau+b_\sigma+(I+J)\Delta = a_\tau+b_\sigma+(K+L)\Delta = a_k+b_l $$

Here is an illustration. You have two large equivalence classes:

enter image description here

You focus on the lines and columns that contain these equivalence classes and chuck the others out for now. Then there are some automatic equivalences depicted below. Equivalence classes are always subsets of antidiagonals, i.e. sets of the form $\{(i,j)\mid i+j=\mathrm{cst}\}$ and are color coded there. For extra clarity I've also added some markings to some of the equivalence classes. Funnily these look like designs straight out of the 1960ies and 1970ies.

enter image description here


Visibility (necessary condition for realizability of $<$)

There is an obvious necessary condition for a total order on $R_{p,q}/\sim$, where $\sim$ is realizable, to be realizable. Suppose $c,d$ are equivalence classes. We say that $d$ is visibly greater than $c$ if there exists some $i$ with $V_i$ intersecting both $c$ and $d$ and such that if $(i,a)\in c$ and $(i,b)\in d$ then $a<b$, or if there is some $j$ with $H_j$ intersecting both $c$ and $d$ and if $(a,j)\in c$ and $(b,j)\in d$ then $a<b$. We allow ourselves to say that $c$ is visibly greater than $d$ if there is a chain $c=c_0,c_1,\dots,c_n=d$ with $c_i$ visibly greater than $c_{i-1}$ (i.e. we consider the transitive closure of the previously defined relation).

Visibility. If $c$ is visibly greater than $d$ then $c<d$.

Visibility is a necessary property satisfied by realizable $<$ but it is not enough.

Counter Example for realizability of $<$

There's more to this, yet. Consider the following discrete equivalence relation (i.e. equivalence classes are singletons) and total order $<$. This total order satisfies all previously proposed conditions but can't arise as a $\sim_{A,B}$ and $<_{A,B}$.

enter image description here

Here's a simpler counter example showing that the individual $3\times 3$ orders are realized.

enter image description here

Horizontal and Vertical Coherence (necessary conditions for realizability of $<$)

The previous example shows that Visibility is not enough to characterize realizable orders. A problem arose where traversing too many horizontal gaps when following $<$ along equivalence classes led to inconsistencies in the values of those gaps. There are some horizontal and vertical consistency conditions that a realizable $<$ must satisfy. Let's start with Horizontal Consistency conditions. Take $(i,j)$ with $1<i$. The sum of the classes containing $(i-1,j)$ and $(i,j)$ differ by $(\Delta a)_i=a_i-a_{i-1}$. If we follow the $<$-path from the $\sim$-class containing $(i-1,j)$ to that containing $(i,j)$ we get $$(\Delta a)_i=\text{sum of positive terms, some $(\Delta a)_{k}$, some $(\Delta b)_l$}$$ from which we extract a condition $$H_{ij}:(\Delta a)_i>\text{sum of some $(\Delta a)_k$ and some $(\Delta b)_l$}$$ where the $(\Delta a)_k$ and $(\Delta b)_l$ to take into account are found using visibility relations. Similarly there are Vertical Consistency conditions of the same ilk $$V_{ij}:(\Delta b)_j>\text{sum of some $(\Delta a)_k$ and some $(\Delta b)_l$}$$ where again, the $(\Delta a)_k$ and $(\Delta b)_l$ that appear on the right hand side are deduced from visibility relations along the $<$-path of equivalence classes linking the $\sim$ equivalence class containing $(i,j-1)$ to the $\sim$ equivalence class containing $(i,j)$


Beginnings of a positive solution for $p=2$

I believe the answer is positive to both questions at least when $p=2$. WLOG we can take $a_1=0$, $a_2=1$ and $b_0=0$. There seems to exist an explicit algorithm to find a rational solution to the problem. I've illustrated it below. The necessary and sufficient condition on $\sim$ in the case $p=2$ seems to be that the lines associated to $2$-element equivalence classes don't intersect. The algorithm is simple but I haven't conceptualized it really:

  • You start with $b_1=0$, the sum in the the lower left corner $(1,1)$ is thus $0$ since $a_1=0$
  • You put $1$ in the lower right corner $(2,1)$, the sum is $1$ since $a_2=1$
  • If the lower right corner is part of a $2$ element equivalence class you put are forced to attribute $1$ to the other member $(1,r)$.
    • if $r>2$ you set $b_r=1$. This is the case in the example below so you set $b_3=1$. Then you are forced to put a $2$ in position $(2,r)$ since $a_2=1$. You keep on going until you don't fall into a 2 element equivalence class.
  • Then you have to insert values for $b_2,\dots,b_{r-1}$. You pick them uniformly apart between $b_1=0$ and $b_r=1$, that is $b_k=\frac{k-1}r$.
  • Then you are forced to inscribe $b_k+1$ on the right hand side. If the right hand side is part of a $2$ element equivalence class you are forced to set the same value for some new $b_s$ etc ...

I hope the picture below (and the color coded rounds) are more explicit than the half-baked algorithm above.

I don't know if this will work for $p\geq 3$.

enter image description here


A connection with topology

$\newcommand{\O}{\mathcal{O}}\newcommand{\R}{\Bbb{R}}$ Fix $\sim$ an equivalence relation on $R_{p,q}$ and $<$ a total order on $R_{p,q}/\sim$. Define $$\O_{p,q}[\sim,<]=\{(A,B)\in\O_p\times\O_q\text{ inducing $~$ and }<\}$$ where $\O_n=\{(x_1,\dots,x_n)\in\R^n\mid x_1<x_2<\cdots<x_n\}$. Then $\O_{p,q}[\sim,<]$ is nonempty iff $(\sim,<)$ is realizable. When it is nonempty it is a convex cell. The $\O_{p,q}[\sim,<]$ partition $\O_p\times\O_q\simeq \R^{p+q}$. It would be interesting to understand the poset structure associated to containment of closures of these. It seems natural to expect:

  • the poset structure is closely related to refinements of $(\sim,<)$;
  • maximal elements correspond to the discrete equivalence relation with the compatible total orders;
  • $(\sim_{A,B},<_{A,B})$ for $A=\{1<2<\cdots<p\}$ and $B=\{1<2<\cdots<q\}$ is minimal but there may be other minimal elements.

Let us put $\newcommand{\real}{\mathfrak{R}}\real_{p,q}$ the set of realizable pairs $(\sim,<)$. We define an order relation on $\real_{p,q}$ by setting $$(\sim,<)\prec(\sim',<')\iff\text{there is an onto map of posets } (R_{p,q}/\sim',<')\to(R_{p,q}/\sim,<)$$

Lemma. Let $(\sim,<),(\sim',<')\in\real_{p,q}$ be realizable. The following are equivalent:

  1. $\overline{\O_{p,q}[\sim,<]}\subset\overline{\O_{p,q}[\sim',<']}$

  2. $\O_{p,q}[\sim,<]\subset\overline{\O_{p,q}[\sim',<']}$

  3. $\O_{p,q}[\sim,<]\cap\overline{\O_{p,q}[\sim',<']}\neq\emptyset$

  4. $(\sim,<)\prec(\sim',<')$

Sketch of Proof. $1$ and $2$ are always equivalent and clearly imply $3$. If we let $(A_n',B_n')\in\O_{p,q}[\sim',<']$ tend to $(A,B)\in\O_{p,q}[\sim,<]$ then what can happen is fusion of $<'$-intervals of $\sim'$-equivalence relations and $<$ and $<'$ have to be compatible which amounts to the existence of an onto homomorphism. This will prove $3\implies 4$. To finish the proof we show that $4\implies 2$. It is enough to notice that if $(\sim,<)\prec(\sim',<')$ and $(A,B)\in\O_{p,q}[\sim,<]$ and $(A',B')\in\O_{p,q}[\sim',<']$ then for all $t\in[0,1)$, $$\qquad\qquad\qquad(tA+(1-t)A', tB+(1-t)B')\in\O_{p,q}[\sim',<'].\qquad\qquad\qquad\square$$

This has desirable homotopical consequences: one can use these cells to compute homotopy colimits of subcategories of the poset $(\real_{p,q,\prec)$ if one ever wanted to do so.


$\endgroup$
22
  • 1
    $\begingroup$ @ErickWong Additive combinatorics makes sense. The connection with configuration spaces is indeed debatable. I included it because (a) it somehow reminded me of Fox Neuwirth cells and (b) I imagine that if one were to consider refinement of these equivalence relations then refinement would be related to closure of sets of pairs of n-tuples defining the same equivalence relation. $\endgroup$ Apr 15, 2021 at 18:07
  • 3
    $\begingroup$ How is this remotely a question for Maths SE? There are at least four separate questions, each of which has more buildup than is expected of a single whole question here. At the very least break it up into the four parts. No question short of a thesis would sufficiently answer all four, and no answer that fully addresses just one could be compared to that which answers one other. $\endgroup$
    – Nij
    Apr 18, 2021 at 8:55
  • 2
    $\begingroup$ @Nij There are really three questions: (1) characterize realizable $\sim$ (2) decide if realizable $\sim$ can be realized with sets of integers and (3) characterize realizable $<$. These questions don't require a build up beyond the definitions given in the first paragraph and are related enough that batching them up in a single post makes sense IMO. The other points are proposals for a characterization and these do require definitions, which is what I provide along with some illustrations. Everything beyond the three questions above represents my work and partial progress. $\endgroup$ Apr 18, 2021 at 9:09
  • 2
    $\begingroup$ This question is certainly elaborated and it took time and work to write it out, which is why I'm hesitant to vote to close it. Yet, I agree with @Nij that it is not the type of question suited for MSE. It looks more like a full (small) research project. Indeed, despite being extraordinarily long it misses important context: where did you come across this problem and why is it relevant to you? $\endgroup$
    – Christoph
    Apr 18, 2021 at 9:14
  • 2
    $\begingroup$ @Christoph It came up when thinking about graded modules $M=\bigoplus_{\lambda\in\Lambda} M_\lambda$ over a graded ring $R=\bigoplus_{\gamma\in\Gamma}$ and thinking about the possible ways in which $R_\gamma \cdot M_\lambda \subset M_{\mu}$ can happen. I drew pictures and was led to drawing blob diagrams of the sort pictured above. I realized that there was a combinatorial question of interest and tried answering that. This led to the question. $\endgroup$ Apr 18, 2021 at 9:22

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.