Demonstração

Em base \(2\), \(f_{D,2}\) tem \(2^{\frac{D}{2}}\) ciclos de período \(1\).

Consideremos os naturais escritos em base \(2\) e a transformação \(f_{D,2}\) a actuar em representações binárias com \(D\) dígitos, permitindo-se zeros à esquerda. O domínio de \(f_{D,2}\) tem \(2^{D}\) elementos; a imagem está reduzida a \(\frac{3^{\frac{D}{2}}+1}{2}\) elementos quando \(D\) é par e tem cardinal \(\frac{3^{\frac{D-1}{2}}+1}{2}\) se \(D\) é ímpar.

Para \(D=2\), a imagem de \(f_{2,2}\) tem \(2\) elementos, \(\{00, 01\}\), e estes são pontos fixos da aplicação. A órbita de qualquer outro elemento do domínio de \(f_{2,2}\) termina num destes pontos fixos ao fim de um iterado.

Para \(D=4\), a imagem de \(f_{4,2}\) tem \(5\) elementos, nomeadamente \(\{0000, 0111, 0101, 0010, 1001\}\) e, destes, os quatro primeiros são pontos fixos; a órbita de \(1001\) termina em \(0000\) ao fim de um iterado. De novo, a órbita de qualquer elemento do domínio de \(f_{4,2}\) termina num destes pontos fixos. Determinámos os pontos fixos resolvendo a equação \(f_{4,2}(n)=n\), sendo \(a_{3}a_{2}a_{1}a_{0}\) a representação binária de \(n\) \((a_{j}\) é \(0\) ou \(1).\) Essa equação resume-se às duas igualdades seguintes: \[7\,(a_{3}-a_{0}) + 2\,(a_{2}-a_{1})= 8a_{3} + 4a_{2} + 2a_{1} + a_{0}\] ou \[7\,(a_{0}-a_{3}) + 2\,(a_{1}-a_{2})= 8a_{3} + 4a_{2} + 2a_{1} + a_{0}.\]

A primeira equação é equivalente \(a_{3} + 2a_{2} + 4a_{1} + 8a_{0} = 0\), e dela concluímos que \(a_{3}=0=a_{2}=a_{1}=a_{0}\), obtendo-se deste modo o ponto fixo \(0\) de \(N_{4}\). A segunda reescreve-se como \[5a_{3} = 2\,(a_{0} - a_{2})\] de onde resulta que \(a_{1}\) é livre em \(\{0,1\}\) e que \(a_{3}=0\) (para que \(5a_{3}\) possa ser par), logo \(a_{0} = a_{2}\). Ou seja, os pontos fixos de \(f_{4,2}\) são as representações binárias \(0a_{0}a_{1}a_{0}\). Isto é, \(0000, 0010, 0111, 0101.\)

Para \(D=6\), deduzimos por processo análogo que os pontos fixos de \(f_{6,2}\) são as representações binárias \(0a_{0}a_{1}a_{2}a_{1}a_{0}\), sendo \(a_{0},\) \(a_{1}\) e \(a_{2}\) livres em \(\{0,1\}\); obtemos \(8\) pontos fixos. A imagem de \(f_{6,2}\) contém \(14\) elementos e todas as órbitas acabam num destes pontos fixos.

Em geral, consideremos que \(D\) é par e determinemos os pontos fixos de \(f_{D,2}\). Para isso, há apenas que resolver a equação \(f_{D,2}(n)=n\), sendo \(a_{D-1}a_{D-2}...a_{1}a_{0}\) a representação binária de \(n\) com \(D\) dígitos \(0\) ou \(1\). Esta equação é equivalente às duas igualdades seguintes: \[(2^{D-1} - 1)(a_{D-1}-a_{0}) + (2^{D-2} - 2)(a_{D-2}-a_{1}) +...+\left (2^{\frac{D}{2}} - 2^{\frac{D}{2}-1}\right)\left(a_{\frac{D}{2}}-a_{\frac{D}{2}-1}\right) =\\ 2^{D-1}a_{D-1} + 2^{D-2}a_{D-2} +...+ 2^{\frac{D}{2}}a_{\frac{D}{2}} +...+ 2a_{1} + a_{0}\] ou \[(2^{D-1} - 1)(a_{0}-a_{D-1}) + (2^{D-2} - 2)(a_{1}-a_{D-2}) +...+ \left(2^{\frac{D}{2}} - 2^{\frac{D}{2}-1}\right)\left(a_{\frac{D}{2}-1}-a_{\frac{D}{2}}\right) =\\ 2^{D-1}a_{D-1} + 2^{D-2}a_{D-2} +...+ 2^{\frac{D}{2}}a_{\frac{D}{2}} +...+ 2a_{1} + a_{0}. (*)\] A primeira equação é equivalente a \[a_{D-1} + 2a_{D-2} +...+ 2^{D-2}a_{1} + 2^{D-1}a_{0} = 0\] e dela concluímos que \(a_{D-1}=0=a_{D-2}=...=a_{1}=a_{0}\), obtendo o ponto fixo \(0\) de \(N_{D}\). A segunda equação é equivalente a \(i_{D,2}(x)=2x\) e reescreve-se como \[2^{D-1}a_{0} + 2^{D-2}a_{1} + ... + 2a_{D-2} + a_{D-1} = 2\,\left(2^{D-1}a_{D-1} + 2^{D-2}a_{D-2}+...+ 2^{\frac{D}{2}}a_{\frac{D}{2}}+...+2a_{1} + a_{0}\right)\] de onde deduzimos de imediato que devemos ter \(a_{D-1} = 0\), caso contrário obtemos um natural ímpar no lado esquerdo da equação e um natural par do lado direito. Assim, a equação (*) reduz-se a \[2^{D-2}a_{0} + 2^{D-3}a_{1}+...+ 2a_{D-3} + a_{D-2} = 2^{D-1}a_{D-1} + 2^{D-2}a_{D-2}+...+ 2^{\frac{D}{2}}a_{\frac{D}{2}}+...+2a_{1} + a_{0}\,\, (2*)\] e daqui concluímos, por razão análoga à anterior, que devemos ter \[a_{D-2} = a_{0}.\]

Isso permite reformular (2*) como \[2^{D-3}a_{0} + 2^{D-4}a_{1}+…+2a_{D-4} + a_{D-3} = 2^{D-2}a_{D-1} + 2^{D-3}a_{D-2}+…+ 2^{\frac{D}{2}-1}a_{\frac{D}{2}}+…+2a_{2} + a_{1} \] e portanto devemos ter \(a_{D-3} = a_{1}\). Prosseguindo desta forma, obtemos a expressão geral da representação binária de um ponto fixo de \(f_{D,2}:\) \[0 a_{D-2} a_{D-3} … a_{\frac{D}{2}} a_{\frac{D}{2}-1} a_{\frac{D}{2}} a_{\frac{D}{2}-1}… a_{D-3} a_{D-2}\] sendo \(a_{D-2}, a_{D-3}, … ,a_{\frac{D}{2}-1}\) e \(a_{\frac{D}{2}}\) livres em \(\{0,1\}\). Encontramos assim \(2^{\frac{D}{2}}\) pontos fixos. (Note-se que, até \(D=16\), todas as órbitas de \(f_{D,2}\) terminam num destes pontos fixos.)