# Given $n>2$ and $1<k<n$. Is it possible to exist $n$ events(probability>0), s.t. for any $k$ among them are independent while any $k+1$ are not?

For example when $$k=2$$, consider $$n+1$$ disjoint events :

$$E=\{ e_0,e_1,...,e_n\}$$ with the probability that $$P(e_0)=a,P(e_i)=b,1\leq i\leq n.$$

We define $$n$$ events $$E_1,E_2,...,E_n$$ such that $$E_i=\{e_0\} \cup\{ e_i \}$$.For any $$1\leq i we obtain:

$$P(E_i)P(E_j)P(E_k)=(a+b)^3,P(E_i)P(E_j)=(a+b)^2,P(E_i \cap E_j)=a,P(E_i\cap E_j\cap E_k)=a.$$

We can easily prove the existence of (a,b) satisfying $$(a+b)^2=a,0 for any given n, which means that for any $$2$$ events are independent while any $$3$$ are not.

So a more genreal question is that given $$n>2$$ and $$1. Is it possible to exist $$n$$ events, s.t. for any $$k$$ among them are independent while any $$k+1$$ are not?

Beased the proof above, we know that k=2 is OK.

• +1 : Very interesting question, nice work shown. Commented Sep 22, 2021 at 7:46

Yes, it is possible.

Let $$F$$ be a finite field with $$|F|>n$$. I will denote $$|F|=q$$, and identify $$F$$ with the set $$\{0,1,\dots,q-1\}$$.

Let $$P$$ be a uniformly randomly chosen polynomial whose degree is less than $$k$$. There are $$q^k$$ equally likely options for $$P$$, of the form $$P(x)=\sum_{j=0}^{k-1}a_jx^j$$ with $$a_j\in F$$ for each $$j\in \{0,\dots,k-1\}$$.

Then, for each $$i\in \{0,1,\dots,n-1\}$$, let $$E_i$$ be the event that $$P(i)=0$$. We can see that $$P(E_i)=1/q$$, since $$P(i)$$ is equally likely to be any element of $$F$$.

Note that $$E_0,E_1,\dots,E_{k-1}$$ is an independent set, since Lagrange interpolation implies that the vector $$(P(0),P(1),\dots,P(k-1))$$ assumes all $$q^{k}$$ possible vectors in $$F^k$$ as $$P$$ ranges over all $$q^k$$ possible polynomials of degree less than $$k$$. However, the collection $$E_0,\dots,E_{k-1},E_{k}$$ is not independent, since $$P(E_0\cap \dots \cap E_{k})=(1/q)^k\neq (1/q)^{k+1}=P(E_0)\cdots P(E_k)$$ as the only polynomial of degree less than $$k$$ with $$k$$ distinct roots is the zero polynomial.

• Your idea looks very elegant. Anyway, I am afraid it does not implicate independence for any group of K variables. For instance for k=2 and n=9 if you choose q=10, you have not independance of $E_0$ and $E_5$. Actually, I have created a python script to check it. I put it in my answer so you can check whether it is correct. Commented Sep 23, 2021 at 16:15
• @ArnaudMégret There do not exist any finite fields with a size of $q=10$. You might be confusing "finite field of size $q$" with $\Bbb Z/q\Bbb Z$; the two are not the same. Commented Sep 23, 2021 at 16:17
• Oh yes, actually I didn't know the term finite fields. I supposed it was an algebra with modulo n operations. Commented Sep 23, 2021 at 16:24
• using n=11 (prime number) seems to provide any independence for 2 variables. Commented Sep 23, 2021 at 16:30

Thanks for @Mike Earnest. I now can write a complete proof.

\textbf{Question:}\ Given $$n>2$$ and $$1. Proof the existence of $$n$$ events whose probability is greater than 0, s.t. for any $$k$$ among them are independent while any $$k+1$$ are not. \

\textbf{Lemma: }\ Given $$k$$ different integers $$\{ i_1,i_2,...,i_k\}$$, $$k$$ integers $$C=( A_1,A_2,...,A_k )^T$$ a $$k \times k$$ matrix $$A$$: $$$$\left[ \begin{array}{ccccc} 1 & i_1 & i_1^2 & \dots & i_1^{k-1} \\ 1 & i_2 & i_2^2 & \dots & i_2^{k-1} \\ \dots & \dots & \dots & \dots & \dots \\ 1 & i_k & i_k^2 & \dots & i_k^{k-1} \\ \end{array} \right ]$$$$ Then given a prime number $$p$$ such that $$p > k$$. Then the following equation have and only have one solution for $$x=( x_1,x_2,...,x_k)^T$$,where $$x_j \in \{0,1,...,p-1\}$$: $$Ax=C.$$

\textbf{Proof of Lemma: }

\qquad We write it in the form of augmented matrix :

$$$$\left[ \begin{array}{cccccc} 1 & i_1 & i_1^2 & \dots & i_1^{k-1} & A_1\\ 1 & i_2 & i_2^2 & \dots & i_2^{k-1} &A_2\\ \dots & \dots & \dots & \dots & \dots & \dots \\ 1 & i_k & i_k^2 & \dots & i_k^{k-1} & A_k \\ \end{array} \right ]$$$$ We use elementary matrix transformation, \textbf{But once we get a $$A_i$$ out of range$$(A_i>p$$ or $$A_i<0)$$ in operation, we keep the remainder of modulo p instead of $$A_i$$}. Notice that this new defined matrix transformation dose not affect the properties of matrix $$A$$. Thus verifying the $$det(A) \neq 0$$ can conduct that $$Ax=C$$ has only one solution. Since we have$$det(A)=\prod_{i>j}^{}{(x_i-x_j)}\neq 0$$, thus we proved.

\textbf{Proof:}

\qquad We now try to show that there exist $$n$$ events such that for any $$k$$ among them are independent while any $$k+1$$ are not.

\qquad For any given $$n$$, we find a prime number $$p$$ ,$$p>n$$. And define a set $$T= \{ 0,1,...,p-1 \}$$. We also define a polynomial $$f(x)=\sum_{i=0}^{k-1}{a_ix^i}$$where $$a_i \in T, 0\leq i \leq k-1$$. All the coefficients of $$f$$ is randomly chosen from $$T$$.

\qquad Then we define $$n$$ events set $$E=\{E_0,E_1,E_2,...,E_{n-1}\}$$. We define $$P(E_i)$$ is the probability of $$p | f(i)$$. We now show that any $$K (K\leq k)$$of them are independent.

\qquad $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_K})$$ means the randomly choose cause $$p | f(s_t),1\leq t \leq K$$. We now calculate the quantity of $$\{ a_0,a_1,...,a_{k-1} \}$$ satisfying the condition $$p | f(s_t)$$ \textbf{for any given $$s_j$$} . Since $$K\leq k$$ so we seperate the coefficients into 2 groups $$A=\{a_0,a_1,...,a_{K-1}\}$$ and $$B=\{a_K,a_{K+1},...,a_{k-1}\}$$ (B may be empty). We let coefficients in B be randomly chosen. \textbf{For any given randomly choose of B}, there is one and only one solution for the coefficients $$a_0,...,a_{K-1}$$ satisfying the K equations below, according to the lemma (if $$K>k-1$$, the RHS=0).

$$\sum_{i=0}^{K-1}{a_is_r^i}=-\sum_{i=K}^{k-1}{a_is_r^i} \ \textup{(mod p)}, 1\leq r\leq K.$$ \qquad Which means that $$p | f(s_t),1\leq t \leq K$$. So the quantity of coefficient satisfying the conditions is exactly what we randomly chose coefficients in $$B$$. There are obviously $$|T|^{|B|}=p^{k-K+1}$$. Thus $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_K})=\frac{|T|^{|B|}}{|T|^{k+1}}=p^{-K}.$$

\qquad Notice that this also works for $$K=1$$, Thus $$P(E_{s_j})=p^{-1}$$, Thus $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_K})=p^{-K}=P(E_{s_1})P(E_{s_2})...P(E_{s_K}).$$

\qquad We have shown that any $$K, K\leq k$$ of them are independent. Now we will show that any $$R, R>k$$ of them are not. We notice that $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_R})$$ needs $$R$$ different roots on the field. The only polynomial still satisfy is zero polynomial(Actually for $$K=k$$ it has been zero polynomial but product of probabilities still hold). Thus, $$P(E_{s_1}\cap E_{s_2}\cap ...\cap E_{s_R})=p^{-k}>p^{-R}=P(E_{s_1})P(E_{s_2})...P(E_{s_R})$$ \qquad Which means that any $$R$$ of them are not independent. Thus we proved.