7
$\begingroup$

This is a followup question to the discussion in the comments of Sets which are not fixed by any non-identity isomorphism

So consider a finite $n$-dimensional vector space $V$ over $F_2$. For which such $n$ does there exist a subset $W$ of $V$ such that $T(W)\neq W$ for any non-identity isomorphism $T:V\to V$.

$n=1$ is trivial, for $n=2,3$ one can see no subset works. For $n=4,5$ perhaps the set $\{e_1,e_2,e_3,e_4,e_1+e_2,e_1+e_2+e_3,e_1+e_2+e_3+e_4,e_1+e_4\}$, with the $e_i$s being a basis, is worth checking. (Or possibly I'm missing something trivial).

It seems interesting to me how one goes about proving if such sets exist or do not exist for all large $n$.

$\endgroup$

3 Answers 3

12
$\begingroup$

For $n=4$ it cannot work: Suppose that no nontrivial element of $G=GL(n,2)$ fixes an element of $W$. Then $V$ has at least $\lvert G\rvert$ subsets of size $k=\lvert W\rvert$, because all the sets $g(W)$, $g\in G$, are distinct.

So a necessary condition is $\lvert GL(n,2)\rvert\le\binom{2^n}{k}$. However, $\lvert GL(4,2)\rvert=20160>12870=\binom{16}{8}\ge\binom{16}{k}$.

For $n\ge5$ this obstruction does not hold anymore. Indeed, experiments show that for $n=5$ there are examples with $k=16$, and for $n\ge6$, apparently most random subsets $W$ of size $2^{n-1}$ work.

An easy counting argument shows that for $n$ sufficiently big, indeed such a set $W$ exists: Let $f$ be the number of fixed point of a nonzero element from $GL(n,2)$. Then $g$ has at most $(2^n-f)/2$ cycles of length $\ge2$ on $V$. So all together, $g$ has at most $2^{n-1}+f/2$ cycles. But $f\le 2^{n-1}$, so any nontrivial $g$ has at most $2^{n-1}+2^{n-2}=2^n-2^{n-2}$ cycles. Each invariant subset of $V$ is a union of such cycles. So there are at most $2^{2^n-2^{n-2}}$ invariant subsets.

Set $M=\{(w,g)|g(w)=w\}$, where $w$ runs through the subsets of $V$, and $g$ through $G\setminus\{1\}$. By what we saw, $\lvert M\rvert\le (\lvert G\rvert-1) 2^{2^n-2^{n-2}}$. On the other hand, if there is no set $W$, then each $w$ is fixed by at least one $g\ne1$, hence $\lvert M\rvert\ge 2^{2^n}$.

We obtain $\lvert G\rvert\gt 2^{2^{n-2}}$. On the other hand, clearly $\lvert G\rvert\le 2^{n^2}$, a contradiction for $n\ge8$. So the cases $n=5,6,7$ probably have to be done by hand (or computer). Indeed, in these cases $W$ exists.

$\endgroup$
1
  • $\begingroup$ In the definition of $M$, you need to exclude $g=1$. $\endgroup$ Aug 6, 2013 at 13:58
3
$\begingroup$

Now that Peter Mueller has shown that solutions exist for large values of $n$, I believe it is worthwhile to give a more explicit construction of a solution. The idea is to work by induction on $n$, seeing $(F_2)^n$ as a linear subspace of $(F_2)^{n+1}$ through the canonical injection $(x_1,\dots,x_n) \mapsto (x_1,\dots,x_n,0)$.

Now, let us assume that, for some integer $n>2$, there exists a subset $W_n$ of $(F_2)^n$ for which the identity is the sole automorphism of $(F_2)^n$ that leaves it invariant. Then, we construct a subset $W_{n+1}$ of $(F_2)^{n+1}$ as follows:

If $|W_n|>2^{n-1}$, we define $W_{n+1}$ as the union of $W_n$ with the set consisting of the sole vector $e_{n+1}:=(0,\dots,0,1)$;

Otherwise, we define $W_{n+1}$ as the union of $W_n$ with the set consisting of all the vectors $(x_1,\dots,x_n,1)$ with $(x_1,\dots,x_n) \neq 0$.

I contend that $W_{n+1}$ is a solution in any case. From there, if one has an explicit solution for an integer $p>3$, then one obtains an explicit solution for all larger values of $p$ by noting that, in the above construction $|W_{n+1}|<2^n$ whenever $|W_n|>2^{n-1}$, whereas $|W_{n+1}|>2^n$ whenever $|W_n|\leq 2^{n-1}$ (this comes from the observation that $1<|W_n|<2^n-1$).

Now, let us prove the claimed statement. Actually, only the first case needs to be considered since the complementary subset of a solution in the whole vector space is another solution. So, let us assume that $|W_n|>2^{n-1}$ and let us consider an automorphism $f$ of $(F_2)^{n+1}$ that leaves $W_{n+1}$ invariant. We set $\mathcal{H}:=e_{n+1}+(F_2)^n$. Here is the key point:


$\mathcal{H}$ is the sole non-linear hyperplane of $(F_2)^{n+1}$ that has at most one common point with $W_{n+1}$.


Proof : Indeed, let $\mathcal{G}$ be a non-linear hyperplane of $(F_2)^{n+1}$ that differs from $\mathcal{H}$; then $\mathcal{F}:=\mathcal{G} \cap (F_2)^n$ is a non-linear hyperplane of $(F_2)^n$, and we claim that it must have several common points with $W_n$: if indeed this were not the case, as $|W_n|>2^{n-1}$, the set $W_n$ should be the union of the translation vector space $F$ of $\mathcal{F}$ with $\{y\}$ for some $y \in \mathcal{F}$; but then at least one non-identity automorphism of $(F_2)^n$ leaves $W_n$ invariant: one simply takes an arbitrary non-identity automorphism of $F$ and extends it to $(F_2)^n$ by requiring that it should fix $y$.


From there the proof is easy: using the above result, one sees that $f$ must leave $\mathcal{H}$ invariant, whence $f$ fixes $W_n \cap \mathcal{H}=\{e_{n+1}\}$ and it leaves $(F_2)^n$ invariant as it is the translation vector space of $\mathcal{H}$. By induction, the second result yields that the restriction of $f$ to $(F_2)^n$ is the identity. Therefore, $f$ is the identity.

$\endgroup$
1
$\begingroup$

To complete the preceding answers, here's an explicit solution for $n=5$:

One denotes by $B$ the set of all vectors of the standard basis of $(F_2)^5$, by $\mathcal{H}$ the hyperplane of $(F_2)^5$ defined by the equation $\sum_{k=1}^5 x_k=1$, and one sets $K=\{(0,1,1,0,0),(0,0,1,1,0),(1,1,1,1,0),(1,1,1,0,1)\}$. Then, $W:=K \cup (\mathcal{H} \setminus B)$ is a solution. What follows is a rough sketch of proof with no resort to computer verifications.


First of all, one checks that, if we denote by $\mathcal{H}'$ the hyperplane defined by the equation $x_3=1$, then $\mathcal{H}$ and $\mathcal{H}'$ are the only non-linear hyperplanes that contain exactly $11$ elements of $W$. Thus, every automorphism of $(F_2)^5$ that leaves $W$ invariant must either leave $\mathcal{H}$ and $\mathcal{H}'$ invariant or swap them. The next step consists in proving that the sole automorphism that leaves $W$ and $\mathcal{H}$ invariant is the identity: this is easily done by noting that such an automorphism $f$ must leave $B$ invariant, whence it has the form $(x_1,\dots,x_5) \mapsto (x_{\sigma(1)},\dots,x_{\sigma(5)})$ for some permutation $\sigma$ of $\{1,\dots,5\}$; then, using the fact that $f$ must also leave $K=W\setminus \mathcal{H}$ invariant, one easily shows that $\sigma=id$.

It remains to prove that there is no automorphism $f$ that swaps $\mathcal{H}$ and $\mathcal{H}'$ and leaves $W$ invariant: assume on the contrary that such a map $f$ exists. Then, $f$ must swap $B=\mathcal{H} \setminus W$ and $B':=\mathcal{H}' \setminus W=\bigl\{(0,0,1,0,0),(1,0,1,0,0),(0,0,1,0,1),(0,1,1,1,1),(1,0,1,1,1)\bigr\}$. Now, $(1,1,1,1,1)$ is the sum of all the vectors in $B$, and also the sum of all the vectors in $B'$, whence $f$ fixes it. Moreover, $f$ fixes $e_3:=(0,0,1,0,0)$ as it is the sole vector of $B \cap B'$. On the other hand, as $f^2$ leaves $W$ and $\mathcal{H}$ invariant, we know from the first step above that $f^2=id$. Finally, a contradiction is obtained by looking at the bijection from $B \setminus \{e_3\}$ to $B' \setminus \{e_3\}$ induced by $f$ and, knowing that $f(e_3)=e_3$, by checking the equality $f^2=id$. One can test all the $24$ cases (tedious). Alternatively, one can reason as follows: one computes the table of all the sums $b+b'$ with $b \in B \setminus \{e_3\}$ and $b' \in B' \setminus \{e_3\}$, and then one uses the following principles to dicard all the possible bijections from $B \setminus \{e_3\}$ to $B' \setminus \{e_3\}$.

  1. $\mathop{im}(f-id) \subset \ker(f-id)$, and therefore $\mathop{rk}(f-id)\leq 2$ by the rank theorem.
  2. The union $\{b+f(b) \mid b \in B \setminus \{e_3\}\} \cup \{(1,1,1,1,1),(0,0,1,0,0)\}$ is included in $\ker(f-id)$, whereas $\{b+f(b) \mid b \in B \setminus \{e_3\}\}$ is included in $\mathop{im}(f-id)$.

One intermediate result is to prove that the map $b \mapsto b+f(b)$ takes only two values on $B \setminus \{e_3\}$, each attained twice. Then, the contradiction is easily found by table-chasing.

$\endgroup$

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.