[seqfan] Re: Injectivity of a(n) = n^2 - XOR(n^2, n)

[David Radcliffe]

I posted this question on Mastodon, and there was a fruitful discussion. Sandra
Snan <https://oeis.org/wiki/User:Sandra_Snan> noted that a(n) makes sense
when n is a negative integer, using the 2's complement representation.
Erling (Alf) Ellingsen proved
<https://infosec.exchange/@steike/110324763684417971> that a(n + 2^k) =
a(n) + 2^k (mod 2^(k+1)) for all n and k. This implies that a(n) induces a
permutation modulo 2^k for every k, therefore a(n) is injective.

I conjecture, with some experimental evidence, that a(n) is also
surjective, i.e. it is a permutation of Z.

On Sun, May 7, 2023 at 7:28 AM <hv at crypt.org> wrote:

> Let L(n) be the index of the least significant bit set in n, so that
> L(n) = k <=> n == 2^k (mod 2^{k+1}). I assume negative integers are
> represented in twos-complement form, so that L(-1) = L(1) = 0, and
> that L(0) is set to some unique value such as -1.
>
> We have XOR(a, b) = a + b - 2 AND(a, b), so a(n) = -n + 2 AND(n^2, n).
>
> Informally: if L(AND(n^2, n)) = k, then there could potentially be a
> collision at n' = n + 2^{k+1} if L(AND(n'^2, n')) > k, but n and n' are
> identical for the first k bits, and so are n^2 and n'^2, so that
> collision does not exist.
>
> I conjecture that L(XOR(n, n')) = L(XOR(a(n), a(n'))) for all n, n' - ie
> that the first bit at which n and n' differ is also the first bit at
> which a(n) and a(n') differ - which would be ample to show injectivity
> (and extend it also to negative n).
>
> Hugo
>
> David Radcliffe <dradcliffe at gmail.com> wrote:
> :Sequence A174375 <https://oeis.org/A174375> is defined by the equation
> a(n)
> := n^2 - XOR(n^2, n), where XOR is bitwise exclusive OR. (In other words,
> :XOR is binary addition without carries.)
> :
> :Computer experiments suggest that this sequence is injective. In fact,
> :there are no repeated values among the first 10^8 terms. This is quite
> :surprising to me, because it doesn't "look" injective -- the graph
> :resembles a Sierpinski triangle on its side.
> :
> :Can anyone prove that this sequence is injective?
> :
> :- David Radcliffe
> :
> :--
> :Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>