10
$\begingroup$

Take $n\geq 1$, and $m_{ij}\in [0,1], 1\leq i,j \leq n$. Under what conditions is it possible to find measurable subsets $X_1,...,X_n$ of, say, $[0,1]$, such that $leb(X_i\cap X_j)=m_{ij}$?

Some relations are necessary, like $m_{ii}\geq m_{ij}$, or the fact that the matrix $(m_{ij})$ must be semi-definite positive, but it does not appear to be sufficient.

The same question holds with $m_{ij}\in \mathbb{R}_+, X_i \subset \mathbb{R}$.

$\endgroup$
2
  • $\begingroup$ One may assume that $m_{ij} < 1$ whenever $i\neq j$ (otherwise it is necessary that $m_{ik}=m_{jk}$ for all $k$, so necessarily $X_i=X_j$ a.e., and one can reduce to a smaller set of indices). In this case, a necessary condition is also that $\delta_{ij}:=m_{ii}+m_{jj}-2m_{ij}$ must be a distance function on {1,..,n}. $\endgroup$ Mar 29, 2012 at 8:27
  • $\begingroup$ Yes indeed, but this is contained in the fact that $(m_{ij})$ must be SDP because $\delta_{ij}=\sum m_{ab} h_a h_b$ with $h_a=1_{a=i}-1_{a=j}$. $\endgroup$ Mar 29, 2012 at 16:54

3 Answers 3

3
$\begingroup$

The discrete version of this problem, where the $X_i$ are subsets of $\{1,2,\ldots,n\}$, is extremely difficult. For example, it includes the questions of the existence of Hadamard matrices and the existence of finite projective planes, which both remain unsolved despite a huge effort. So one can't expect to have necessary and sufficient conditions that are routine to check. It could be that the continuous problem is easier than the discrete one, though it isn't obvious to me. Actually I think the case when the $\{m_{ij}\}$ are integers is the same as the discrete problem since then each of the sets can be written as the disjoint union of atoms of measure 1.

$\endgroup$
4
  • $\begingroup$ Thanks for this very interesting remark, I will have to check these problems. Would you recommand some references? It might be related to the last question in my statement. $\endgroup$ Apr 1, 2012 at 10:41
  • $\begingroup$ The Wikipedia article "Hadamard matrix" gives the definition. Multiply some columns so that the first row has only $+1$, then replace all $-1$s in the matrix by 0. All rows but the first must have $n/2$ 1s and the intersection of any two of them has $n/4$ 1s. Nobody knows if this is possible whenever $n$ is a multiple of 4. A finite projective place of order $n$ is a collection of $n^2+n+1$ subsets of a set of size $n^2+n+1$ such that each subset has size $n+1$ and any pair of them have exactly 1 element in common. Nobody knows if this is possible for $n=12$, for example. $\endgroup$ Apr 1, 2012 at 11:00
  • $\begingroup$ We know it is not possible for $n=6$ but there is a rational solution. $\endgroup$ Apr 4, 2012 at 5:00
  • $\begingroup$ I think this problem is more difficult than the original problem, because in Hadamard problem everything comes from the fact that you live in a space with cardinality $n$ (with $2^n$ or infinity, the problem is trivial). $\endgroup$ Apr 4, 2012 at 5:20
3
$\begingroup$

Here is a partial idea where the last step needs a bit more justification which doesn't work as well as I had hoped, but may yet have promise.

As noted, this is a question about adding real numbers, no specialized measure theory is involved although the language is convenient. We will had hoped to define $2^n$ values $t_I$, one for each $I \subseteq [n]=\lbrace1,2,\cdots,n\rbrace $ so that if they are all non-negative, then the specified values can be achieved, otherwise they can not.

Suppose that we have a set $U$ of size (or measure) $m_{\emptyset}=|U|$ along with $n$ subsets $X_i$ for $i \in [n]$ each with complement $\overline{X_i}.$ For each $I \subseteq [n],$ let $m_I=|\cap_{i \in I}X_i|$ while $t_I=|(\cap_{i \in I}X_i) \cap (\cap_{j\notin I}\overline{X_j})|.$ As in the problem we can abbreviate $m_i=m_{i,i}$ for $m_{\lbrace i \rbrace}=|X_i|$ and $m_{i,j}$ for $m_{\lbrace i,j\rbrace}=|X_i\cap X_j|.$

If we know either set of values we can uniquely find the others: $$m_I=\sum_{I \subseteq J \subseteq [n]}t_J\hspace{0.1in} \text{ while } t_I=\sum_{I \subseteq J \subseteq [n]}(-1)^{|J|-|I|}m_J$$

If the $m_I$ are given, then the $t_I$ will be determined over the reals, but we want non-negative values. In the given problem we have only $n+\binom{n}{2}$ of the $m$ values, perhaps along with $m_{\emptyset}=1.$

So we first define the rest of the $m_I$ by $m_I=\min_{i,j \in I}m_{i,j}$ then solve for the $t_I$ and check that they are non-negative. I think that these choices will make $t_{[n]}$ as large as possible and thought that they would give all the $t_I$ the best chance to be non-negative consistent with the given information.

BUT now I notice problems with the simple case of asking for the sides of a triangle: $|U|=3$ $|X_1|=|X_2|=|X_3|=2$ and $|X_1 \cap X_2|=|X_1 \cap X_3|=|X_2 \cap X_3|=1$ If we do add the final condition $m_{\lbrace 1,2,3 \rbrace}=|X_1 \cap X_2 \cap X_3|=0$ then we do get the desired solution $t_{\{1,2\}}=t_{\{1,3\}}=t_{\{2,3\}}=1$ with the rest of the $t_I=0.$ HOWEVER if we make my suggested choice of $m_{\lbrace 1,2,3 \rbrace}=|X_1 \cap X_2 \cap X_3|=1$ then we do get $t_{\{1,2,3\}}=1$ as large as possible but then $t_{\{1,2\}}=t_{\{1,3\}}=t_{\{2,3\}}=0$ making $t_{\{1\}}=t_{\{2\}}=t_{\{3\}}=1$ and finally $t_{}=-1$

Think of the values $t_I$ as weights to be assigned to the regions of an ideal Venn diagram for $n$ sets. The conditions on the $m_i$ and $m_i,j$ (along perhaps with $m_{\emptyset}=1$) give $\frac{n^2+n}2$ (or else $\frac{n^2+n}2+1$ ) equations in $2^n$ variables $t_I$ along with the side condition that all the $t_I \ge 0.$ This is a linear programming problem. Perhaps there is a way to start with my assignmet and then adjust the values until success or proved failure, but I am not sure.

later The convex hull might be unworkable once the number of dimensions is $43$ or $43+\binom{43}{2}$ or $2^{43}$, but maybe not. I found the comments on integral problems pretty convincing and asked this question. However I subsequently answered it and realized that, while there is no projective plane of order $6$, We can achieve $m_{\emptyset}=43, m_i=7$ for $1 \le i \le 43$ and all $m_{i,j}=1$ by setting $|t_I|=0$ except that $|t_J|=1/\binom{41}{5}$ for all $\binom{43}{7}$ choices of $J$ with $|J|=7.$ So now I am back to thinking that there might be a simple algorithm which achieves the constraints with least $L_1$ error (so $0$ if possible.)

$\endgroup$
1
  • $\begingroup$ This "Venn-diagram" approach is interesting, but I've been struggling with it without any results... Still it might be relevant to find the covariances on the border of the class of solutions. More clearly, understanding the convex $Q_n$ Pietro mentioned above boils down to understanding its facets, i.e. its boundaries. It is maybe related in your approach to find parameters $t_I$ where you have no more degree of freedom in one direction, meaning you lie on the boundary of $Q_n$. $\endgroup$ Apr 1, 2012 at 10:48
3
$\begingroup$

The set of symmetric $n\times n$ matrices $Q$ that one produces this way, is the convex polytope whose vertices are exactly the $2^n$ binary matrices $\chi_{A\times A}$, for $A\subset[n]:=\{1,\dots,n\}\, .$ I guess this object is well-known.

Given a family of $n$ subsets $X_i$ of $X:=[0,1]$, we may consider the usual construction of the refinement of it, defined by the $2^n$ disjoint sets $$\Xi_A:=\cap_{i\in A} X _ i\setminus \cup _ {i\notin A} X _ i\, , \qquad A\subset [n]\, .$$ Clearly, the $2^n$ numbers $m _ A:=\operatorname{meas}(\Xi_A)$ are non-negative real numbers summing to $1$; conversely, any point $\xi$ of the standard simplex $S$ spanned by the canonical basis $\{\operatorname{e} _ A\}_{A\subset [n]}$ of $ \mathbb{R}^{2^n}$ is produced this way by some family $\{X_i\}_{i\in[n]}$, since one can pass through a convenient family of disjoint sets $\Xi_A$ with $ \operatorname{meas}(\Xi_A)=\xi _ A$ and define $X_i:=\cup_{A\ni i} \Xi _ A $ .

Now consider the linear map $L:\mathbb{R}^{2^n}\ni \xi\mapsto m\in\mathbb{R}^{n^2}$ such that $m_{ij}:=\sum_{A\supset\{i,j\}} \xi _ A$. By the preceding observation, $L(S)=Q$, which proves that $Q$ is a convex polytope spanned by the $L(\operatorname{e} _ A)=\chi_{A\times A} $ for $A\subset[n]:=\{1,\dots,n\}\, .$

It remains to show that the $\chi_{A\times A}$ are convexly independent. Assume $\chi_{B\times B}$ is a convex combination of the $\chi_{A\times A}$ ,

$$ \chi_{B\times B}=\sum _ A c _ A \, \chi_{A\times A} \, .\qquad (1)$$ By restriction to the diagonal of $[n]\times[n]$ it follows $$ \chi _ B=\sum _ A c _ A \, \chi _ A \, ,\qquad(2)$$ so in particular $A\subset B$ for all $A$ corresponding to non-zero coefficients $c _A$ . Also, summing over all $i\in [n]$ in (1) $$|B|\\ \chi _ B = \sum _ A c _ A \, |A|\, \chi _ A , $$ and using (2) $$ \sum _ A c _ A \, \left (|B|- |A|\right) \, \chi _ A = 0, $$ and we conclude that the only non-zero coefficient is $c _ B =1$.

Rmk. Any atom-less probability space of course gives the same conclusion.

$\endgroup$
7
  • $\begingroup$ All you say is true, and I think it is a good way to see it. This convex polytope is not well known, and the problem of efficiently characterising a convex polytope given its extreme points is very difficult: If I give you a matrix, what effective checking will you do to know whether it is in the polytope or not? At this stage there is an infinity of conditions to fulfill. I want to reduce them to the minimum. $\endgroup$ Mar 29, 2012 at 21:41
  • $\begingroup$ I guess the next step should be to present that polytope as an intersection of half-spaces (one for each face) of its linear span (the range of L), so that the final answer is given by a finite number of linear inequalities and equations. A key point is to understand which sets of vertices $v_A:=\chi_{A\times A}$ do span a face (I guess the idea is that the corresponding sets $A$ are somehow close to each other). Hopefully this may be easier than for a general polytope, given that $Q$ has a lot of isometries (e.g. the ones coming from permutations of $[n]$). $\endgroup$ Mar 29, 2012 at 22:23
  • $\begingroup$ At, say, $n=9$, the polytope has $2^{n}=512$ vertices, in dimension $n(n+1)/2=38$, which makes me think we cannot go very far like this... $\endgroup$ Mar 30, 2012 at 5:54
  • $\begingroup$ yes.... this polytope $Q_n$ has $2^n$ vertices, but looks like having a smaller number of faces (e.g. an hypercube has $2^n$ vertices but only $2n$ faces). I think the next step should be understanding the abstract simplicial structure of $Q_n$ (i.e., on the vertex set $\mathcal{P}([n])$. Possibly exploiting an inductive construction. Once one knows the faces, it could be easier to present $Q_n$ as intersection of semi-spaces. $\endgroup$ Mar 30, 2012 at 14:30
  • 1
    $\begingroup$ I also know that any two points of $Q_n$ form a $2$-dimensional facet, and as a corollary that any $3$ sets form a $3$-dimensional facet. I guess that for dimensions higher than $3$, there exist convex polytopes, such as $Q_n$, that are not simplexes but where every segment is a facet. $\endgroup$ Mar 31, 2012 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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