Lo que sigue es una respuesta parcial con una posibilidad razonable de ser convertida en una más plena.
Una familia de subconjuntos de a $\mathcal{F}$ del conjunto finito $[1,\ldots,n]$ es un distintivo de la familia iff para cualquiera de los dos distintos $A,B \subseteq [1,\ldots,n]$ existe $X \in \mathcal{F}$ tal forma que:
$$ |A\cap X| \neq |B\cap X| $$
El reclamo es que existe una distinción de la familia $\mathcal{F}$ la satisfacción de:
$$ |\mathcal{F}| \leq \frac{(2 + o(1)) n}{\log_3 n} $$
Dejando $|\mathcal{F}| = m$, una declaración equivalente es:
$$ \frac{n}{m \log_2 n} \geq \frac{1}{2} \log_3 2 - o(1) $$
con $\frac{1}{2} \log_3 2 \approx 0.31546$.
Somos capaces de mostrar la existencia de una infinidad de $n$ por lo que este puede ser encontrado.
El problema de encontrar un pequeño(est), distinguiendo familia $\mathcal{F}$ puede ser reformulado en términos de un binario (cero/uno) $m\times n$ matriz $M$ tal que la multiplicación por $M$ es inyectiva (uno a uno) mapa de $\{0,1\}^n$ a $\mathbb{N}^m$. Aquí el $m$ filas de $M$ son representaciones binarias de la $m$ conjuntos de $X_i$ pertenecientes a $\mathcal{F}$.
Si $M_{ij} = 1$ al $j \in X_i$ y cero en caso contrario, y si $\vec{b}$ es una columna s.t. $b_i = 1$ al $i \in B \subseteq [1,\ldots,n]$ y cero de otra manera, entonces:
$$ M\vec{b} = (|B\cap X_i| : i=1,\ldots,m)^T $$
Ya que cada subconjunto $B \subseteq [1,\ldots,n]$ está representado por algunos $\vec{b} \in \{0,1\}^n$, $\mathcal{F}$ es un distintivo de la familia si y sólo si todas las imágenes de $M\vec{b}$ son distintos, es decir,$|M\{0,1\}^n| = 2^n$.
La inyectividad de la multiplicación por $M$ $\{0,1\}^n$ es más débil condición de tener rango de $n$, es decir, de inyectividad en todas las $\mathbb{N}^n$. La menor de la matriz binaria inyectiva ejemplo de multiplicación con rango de$(M) \lt n$ parece ser uno como este:
$$ M = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \end{pmatrix} $$
que corresponde a la distinción de la familia $\{\{1,2,3\},\{1,2,4\},\{1,3,4\}\}$ de los subconjuntos de a $\{1,2,3,4\}$.
Formular el problema de la multiplicación de la matriz de los términos permite que los métodos algebraicos para ser utilizado. En particular, un problema un poco diferente es considerada en relación con Code Division Multiple Access (CDMA) de los sistemas en un papel en 2009 por Sh. Dashmiz, P. Pad, F. Marvasti:
Nuevos Límites para los Binarios y Ternarios Sobrecargado CDMA
Una construcción explícita se da allí para antipodal binario $m\times n$ matrices $A$ que son inyectiva en a $\{\pm 1\}^n$, donde por antipodal binario, nos referimos a las entradas de $A$ provienen de $\{\pm 1\}$. Dado un $m\times n$ solución, la construcción proporciona una es $2m\times (2n + m - 1)$.
La multiplicación por cualquier $m\times n$ matriz $A$ ser inyectiva en a $\{\pm 1\}^n$ implica que también es inyectiva en a $\{0,1\}^n$. Para ello, de aplicar la inyectiva afín a la asignación de $\vec{b} \to 2\vec{b}-\vec{1}$, de modo que si la multiplicación por $A$ de dos vectores binarios en $\{0,1\}^n$ le da igual las imágenes, entonces ya multiplicación por $A$ de dos vectores en $\{\pm 1\}^n$ habría dado igual las imágenes. A la inversa argumento es similar, y de ahora en adelante nos referiremos a inyectiva la multiplicación de la matriz sin mención de si $\{\pm 1\}^n$ o $\{0,1\}^n$ es el dominio subyacente.
Aún más: Si $A$ $m\times n$ antipodal de la matriz binaria con inyectiva multiplicación, luego de una $(m+1)\times n$ 0,1-matriz binaria $M$ con inyectiva multiplicación puede ser formado a partir de $A$ añadiendo una fila $[1,1,\ldots,1]$ y el uso de operaciones elementales con sus filas para borrar cualquier información negativa en $A$. Además, el antipodal de la matriz binaria puede siempre ser elegido tener ya una fila de todos, por lo que la necesidad de agregar una fila adicional cuando la conversión de antipodal binario a 0,1-matriz binaria siempre puede ser evitado.
A partir de una variedad de $m\times n$ inyectiva binario de matrices, la relación $\frac{n}{m \log_2 n}$ generado por la recursividad $(m,n) \to (2m,2n+m-1)$ permanece por encima de $\frac{1}{2} \log_3 2$. Sin embargo, estos recursiva secuencias que tiene lagunas en la $n$ de los valores representados, y que todavía no está claro que el obligado puede ser establecido para todos los valores intermedios.
