Skip to main content
added 758 characters in body
Source Link
Will Sawin
  • 148.5k
  • 9
  • 324
  • 563

If we choose $s$ and $t$ at random then the probability eacha point $P$ does not lie in the union of the $S_i$ is $(1- p^{-1})^n$,$(1- (p-1)^{-1})^{k(P)}$ where $k(P)$ is the number of nonzero entries of $P$ and the the probability this point$P$ does not lie in the union of the $t_i$ is $(1-p^{-1})^n$$(1-(p-1)^{-1})^{k'(P)}$ where $k'(P)$ is the number of nonzero coefficients of $P$ expressed in terms of $W$, and these two events are independent, so the probability each point does not lie in the union of the $S_i$ and $T_i$ is $(1-p^{-1})^{2n}$$(1-(p-1) ^{-1})^{k(P)+k'(P)}$ and so the union of the $S_i$ and $T_i$ has size, in expectation, at least $$ p^n ( 1- (1-p^{-1})^{2n}).$$$$p^n - \sum_{x \in \mathbf F_p^n} (1-(p-1) ^{-1})^{k(x)+k'(x)}.$$ The distribution of values of the functions $k$ and $k's $ is independent of the choice of $W$. The product of two functions, subject to the condition that the distribution of the values of the two functions is fixed (and identical), is maximized when the two functions are equal, so this expectation is at most

$$p^n - \sum_{x \in \mathbf F_p^n} (1-(p-1) ^{-1})^{k(x)+k(x)} = p^n - ( 1 + (p-1) (1-(p-1) ^{-1})^2)^n $$ $$= p^n \left( 1 - \left(\frac{p^2 -3p+3 }{p(p-1)} \right)^n\right)$$

Since this is the expected size it is a lower bound for the maximum size. Since this works for every $W$, it is a lower bound for the min-max.

On the other hand, for $W$ the standard basis, we can't do better than choosing $s_i \neq t_i$ for all $i$ which gives a union of size $$ p^n ( 1- (1- 2p^{-1})^n)$$ so this gives an upper bound for the min-max.

These two bounds are not very far from one another, since $$ \frac{p^2 -3p+3 }{p(p-1)} - (1-2 p^{-1} )=\frac{1}{p(p-1)}$$ but both arguments are pretty simple and it may beso it's possible to sharpen either onecan be improved.

If we choose $s$ and $t$ at random then the probability each point does not lie in the union of the $S_i$ is $(1- p^{-1})^n$, the probability this point does not lie in the union of the $t_i$ is $(1-p^{-1})^n$, and these two events are independent, so the probability each point does not lie in the union of the $S_i$ and $T_i$ is $(1-p^{-1})^{2n}$ and so the union of the $S_i$ and $T_i$ has size, in expectation, at least $$ p^n ( 1- (1-p^{-1})^{2n}).$$

Since this is the expected size it is a lower bound for the maximum size. Since this works for every $W$, it is a lower bound for the min-max.

On the other hand, for $W$ the standard basis, we can't do better than choosing $s_i \neq t_i$ for all $i$ which gives a union of size $$ p^n ( 1- (1- 2p^{-1})^n)$$ so this gives an upper bound for the min-max.

These two bounds are not very far from one another, but both arguments are pretty simple and it may be possible to sharpen either one.

If we choose $s$ and $t$ at random then the probability a point $P$ does not lie in the union of the $S_i$ is $(1- (p-1)^{-1})^{k(P)}$ where $k(P)$ is the number of nonzero entries of $P$ and the the probability $P$ does not lie in the union of the $t_i$ is $(1-(p-1)^{-1})^{k'(P)}$ where $k'(P)$ is the number of nonzero coefficients of $P$ expressed in terms of $W$, and these two events are independent, so the probability each point does not lie in the union of the $S_i$ and $T_i$ is $(1-(p-1) ^{-1})^{k(P)+k'(P)}$ and so the union of the $S_i$ and $T_i$ has size, in expectation, at least $$p^n - \sum_{x \in \mathbf F_p^n} (1-(p-1) ^{-1})^{k(x)+k'(x)}.$$ The distribution of values of the functions $k$ and $k's $ is independent of the choice of $W$. The product of two functions, subject to the condition that the distribution of the values of the two functions is fixed (and identical), is maximized when the two functions are equal, so this expectation is at most

$$p^n - \sum_{x \in \mathbf F_p^n} (1-(p-1) ^{-1})^{k(x)+k(x)} = p^n - ( 1 + (p-1) (1-(p-1) ^{-1})^2)^n $$ $$= p^n \left( 1 - \left(\frac{p^2 -3p+3 }{p(p-1)} \right)^n\right)$$

Since this is the expected size it is a lower bound for the maximum size. Since this works for every $W$, it is a lower bound for the min-max.

On the other hand, for $W$ the standard basis, we can't do better than choosing $s_i \neq t_i$ for all $i$ which gives a union of size $$ p^n ( 1- (1- 2p^{-1})^n)$$ so this gives an upper bound for the min-max.

These two bounds are not very far from one another since $$ \frac{p^2 -3p+3 }{p(p-1)} - (1-2 p^{-1} )=\frac{1}{p(p-1)}$$ but both arguments are simple so it's possible either can be improved.

Source Link
Will Sawin
  • 148.5k
  • 9
  • 324
  • 563

If we choose $s$ and $t$ at random then the probability each point does not lie in the union of the $S_i$ is $(1- p^{-1})^n$, the probability this point does not lie in the union of the $t_i$ is $(1-p^{-1})^n$, and these two events are independent, so the probability each point does not lie in the union of the $S_i$ and $T_i$ is $(1-p^{-1})^{2n}$ and so the union of the $S_i$ and $T_i$ has size, in expectation, at least $$ p^n ( 1- (1-p^{-1})^{2n}).$$

Since this is the expected size it is a lower bound for the maximum size. Since this works for every $W$, it is a lower bound for the min-max.

On the other hand, for $W$ the standard basis, we can't do better than choosing $s_i \neq t_i$ for all $i$ which gives a union of size $$ p^n ( 1- (1- 2p^{-1})^n)$$ so this gives an upper bound for the min-max.

These two bounds are not very far from one another, but both arguments are pretty simple and it may be possible to sharpen either one.