計算理論・ラムダ計算の問題

巡回シフト $\sigma (x_1,\dots ,x_7)=(x_2,\dots ,x_7,x_1)$ が生成する位数 $7$ の巡回群 $G=⟨\sigma ⟩$ が $\{0,1{\}}^7$ に作用している。条件 $(1)$ は $f(\sigma x)=f(x)$ ということであり、これは $f$ が $G$ の各軌道上で一定であることと同値である。したがって、条件 $(1)$ を満たす $f$ は「各軌道に $0$ か $1$ を割り当てる方法」と 1 対 1 に対応する。

軌道の個数. バーンサイドの補題を使う。単位元はすべての $2^7=128$ 点を固定する。${\sigma }^k(1\le k\le 6)$ については、$\gcd (k,7)=1$ なので ${\sigma }^k$ も $G$ を生成し、${\sigma }^k$ で固定される点は全成分が等しい点 $0000000,1111111$ の $2$ 点だけである。よって軌道の個数は $$\frac{1}{7}\left(128+6\cdot 2\right)=\frac{140}{7}=20.$$

自己双対性. 補元写像 $c(x)=(1-x_1,\dots ,1-x_7)$ は $\sigma$ と可換（$c\circ \sigma =\sigma \circ c$）なので、軌道 $O$ を軌道 $c(O)$ に写す。$c\circ c=\mathrm{id}$ だから、これは $20$ 個の軌道の集合上の対合である。また、$x$ の重み（$1$ の個数）を $w(x)$ とすると $w(c(x))=7-w(x)$ であり、軌道内では重みが一定である。$7$ は奇数なので $w\ne 7-w$ であり、$c(O)\ne O$ となる。すなわちこの対合には固定点がなく、$20$ 個の軌道は $c$ で互いに写り合う $10$ 組の対 $\{O,c(O)\}$ に分かれる。

条件 $(1)$ を満たす $f$ が条件 $(2)$ を満たすことは、各対 $\{O,c(O)\}$ について「$c(O)$ 上の値 $=1-$（$O$ 上の値）」となることと同値である。よって各対について $O$ 上の値を $0$ か $1$ に自由に選べば、$c(O)$ 上の値は一意に決まる。逆に、こうして定めた $f$ は $(1)$ と $(2)$ を満たす。

したがって求める個数は $$2^{10}=1024.$$

条件 $(1)$ より $f$ は巡回置換 $\sigma :(x_1,\dots ,x_7)\mapsto (x_2,\dots ,x_7,x_1)$ の軌道上で定数。$\{0,1{\}}^7$ の軌道の個数を数える。7 は素数なので、$\sigma$ で動かない点は $0000000$ と $1111111$ の 2 個だけで、残り $2^7-2=126$ 個は大きさ 7 の軌道に分かれ、その数は $126/7=18$。合計 $20$ 個の軌道がある。$f$ は軌道ごとに値を決める関数と同一視できる。

補集合をとる操作 $c:x\mapsto \bar{x}$ は $\sigma$ と可換なので、軌道の集合に作用する。条件 $(2)$ は、軌道 $O$ に対して $f(\bar{O})=1-f(O)$ を要求する。

もし $c(O)=O$ なら $f(O)=1-f(O)$ となり不可能。ところが $c(O)=O$ となる軌道は存在しない: $x\in O$ のとき $\bar{x}\in O$ なら $\bar{x}$ は $x$ の巡回シフトで、シフトは 1 の個数（重み）を変えないが、重みは $k$ から $7-k$ になるので $k=7-k$、$k=3.5$ となり矛盾。（$0000000$ と $1111111$ も互いに入れ替わる別々の軌道。）

したがって 20 個の軌道は補集合で $10$ 組のペア $\{O,\bar{O}\}$ に分かれる。各ペアで $f(O)$ を自由に選べば（0 か 1）、$f(\bar{O})=1-f(O)$ で決まる。ゆえに条件を満たす $f$ の個数は $2^{10}=1024$。