Finding maximal number of bad triplets

86 Views Asked by At

Let $a,b,c\in \mathbb{F}_{3^n}$. The summation of two vectors is done with modulo $3$. The elements of vectors are $0,1$ or $2$. We will say that $a,b,c$ form a bad triplet if $a\neq b,a\neq c,b\neq c$ and $a+b+c=0$.

Let $B_k$ be maximal number of bad triplets of set that has $k$ vectors. So we should add vectors to set so that number of total bad triplets in set is maximized.

I have calculated some values of $B_k$.

$B_1 = B_2 = 0,\ B_3 = B_4=1,\ B_5=2,\ B_6=3,\ B_7=5,\ B_8=8,\ B_9=12\ ...$

I need formula for $B_k$ or some evaluation of it. Tried here but no result.

For example (for $n = 2$) the set that produces $B_6=3$ may be $\{(0,0),(1,0),(2,0),(0,1),(1,1),(0,2)\}$

$(0,0)+(1,0)+(2,0) = (0,0)$

$(0,0)+(0,1)+(0,2) = (0,0)$

$(0,2)+(1,1)+(2,0) = (0,0)$

So we have $3$ bad triplets.

I believe that value of $B_k$ doesn't depend on $n$ (size of vectors). I have already showed that $B_k \le$ $\frac{{k} \choose {2}}{3}$ but need more correct formula.

1

There are 1 best solutions below

0
On

Considering only the $j^{\operatorname{th}}$ coordinate, there are only two possibilities: either $a_j=b_j=c_j$, or all three are distinct. In other words, you are counting the maximum number of Sets that may be made with $k$ cards and $n$ properties!

I know of a decent amount of research about the opposite problem, that of finding the largest possible subsets of $\mathbb{F}_3^n$ that contain no such triples. Here is a post by Terence Tao on the subject, for example. But I don't know offhand about research specifically on your problem.

Note that ${a,b,c}$ is a "bad" triplet if and only if it forms a line in $\mathbb{F}_3^n$. This is an important geometric interpretation that might help in finding similar work. Who knows, maybe somebody has applied algebraic geometry to this...