[seqfan] Re: Injectivity of a(n) = n^2 - XOR(n^2, n)
Fred Lunnon
fred.lunnon at gmail.com
Tue May 30 02:46:32 CEST 2023
////////////////////////////////////////////////////////////////////////////////
David Radcliffe:
<< I conjecture, with some experimental evidence, that a(n) is also
surjective,
i.e. it is a permutation of Z. >>
I have eventually proved this claim, utilising or more frequently abusing
(which explains why it took three weeks) some elementary p-adic analysis.
Below follows a sketch of the argument, in anticipation of the completion
of
any detailed justification involving further protracted circumvention of
its
author's inconvenient propensity for commission of footling category
errors.
[Unambiguous function definitions rendered in Magma CAS: please advise if
incomprehensible! Should mailer interference have garbled my meticulous
spacing, a text file copy of this post may sneak past as an attachment ...]
// Carl White's sequence a(n) given integer n , see OEIS A174375.
function CW(n) return n^2 - BitwiseXor(n^2, n); end function;
// Fred Lunnon's mystery sequence, given integer u .
function FL(u)
local n; n := 0; while (CW(n)-u) ne 0 do n := n + (CW(n)-u); end
while;
return n; end function;
FL(u) is constructed via Hensel lifting to solve equation CW(n)-u = 0 ,
observing that the 2-adic derivative exists and equals -1 .
Lemma (Ellingsen): for integer n and natural k ,
CW(n + 2^k) == CW(n) + 2^k (mod 2^(k+1)) .
This generalises inductively: for integer j ,
CW(n + 2^k j) == CW(n) + 2^k j (mod 2^(k+1)) .
Lemma: for natural k and integer n where n^2 < 2^k , there holds
CW(n + 2^k) = CW(n) - 2^k , exactly.
This generalises inductively to the right only: for natural j there holds
CW(n + 2^k j) = CW(n) + 2^k j ;
which fails for integer j < 0 (a non-Archimedean booby-trap!).
Lemma: CW(n) and FL(u) are well-defined;
the latter function termination an indirect consequence of the previous
lemma.
Lemma: CW(n) and FL(u) are injective, via Ellingsen.
Theorem: CW(n) and FL(u) are inverse functions: for all integer n, u,
FL(CW(n) = n and CW(FL(u) = u .
Corollary: CW(n) and FL(u) permute the integers. ***
Fred Lunnon
____________________
Function tables with columns respectively
[ n, CW(n), CW(-n), FL(n), FL(-n) ] for 0 <= n <= 64 ;
all presumptive candidates for OEIS!
[ 0 0 0 0 0]
[ 1 1 3 1 3]
[ 2 -2 10 6 2]
[ 3 -1 21 -1 5]
[ 4 -4 36 28 4]
[ 5 -3 55 13 7]
[ 6 2 70 58 14]
[ 7 -5 105 11 9]
[ 8 -8 136 120 8]
[ 9 -7 171 25 59]
[ 10 -10 210 -2 10]
[ 11 7 237 23 29]
[ 12 -12 300 20 12]
[ 13 5 335 21 15]
[ 14 -6 398 114 22]
[ 15 -13 465 51 17]
[ 16 -16 528 496 16]
[ 17 -15 595 49 19]
[ 18 -18 666 54 18]
[ 19 -17 741 47 245]
[ 20 12 788 236 52]
[ 21 13 871 -3 55]
[ 22 -14 982 42 30]
[ 23 11 1049 27 121]
[ 24 -24 1176 104 24]
[ 25 9 1243 1001 107]
[ 26 -26 1378 110 26]
[ 27 23 1437 39 237]
[ 28 4 1564 484 60]
[ 29 -11 1695 101 31]
[ 30 -22 1822 226 102]
[ 31 -29 1953 99 33]
[ 32 -32 2080 2016 32]
[ 33 -31 2211 97 35]
[ 34 -34 2346 38 34]
[ 35 -33 2485 95 37]
[ 36 -36 2628 -4 36]
[ 37 -35 2775 45 231]
[ 38 34 2854 218 46]
[ 39 27 3017 43 41]
[ 40 -40 3240 88 40]
[ 41 -39 3403 57 219]
[ 42 22 3506 222 1002]
[ 43 39 3661 119 61]
[ 44 -44 3916 244 44]
[ 45 37 4015 53 111]
[ 46 -38 4270 82 246]
[ 47 19 4401 83 497]
[ 48 -48 4656 464 48]
[ 49 17 4787 209 115]
[ 50 -50 5050 86 50]
[ 51 15 5189 79 85]
[ 52 -20 5428 204 84]
[ 53 45 5575 93 87]
[ 54 18 5814 74 62]
[ 55 -21 6073 -5 985]
[ 56 -56 6328 72 56]
[ 57 41 6459 73 459]
[ 58 6 6722 78 122]
[ 59 -9 6973 199 77]
[ 60 -28 7228 964 92]
[ 61 -43 7487 197 63]
[ 62 -54 7742 450 70]
[ 63 -61 8001 195 65]
[ 64 -64 8256 8128 64]
////////////////////////////////////////////////////////////////////////////////
On Sun, May 7, 2023 at 2:59 PM David Radcliffe <dradcliffe at gmail.com> wrote:
> 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
-------------- next part --------------
////////////////////////////////////////////////////////////////////////////////
I have eventually proved this claim, utilising or more frequently abusing
(which explains why it took three weeks) some elementary p-adic analysis.
Below follows a sketch of the argument, in anticipation of the completion of
any detailed justification involving further protracted circumvention of its
author's inconvenient propensity for commission of footling category errors.
[Unambiguous function definitions rendered in Magma CAS: please advise if
incomprehensible! Should mailer interference have garbled my meticulous
spacing, a text file copy of this post may sneak past as an attachment ...]
// Carl White's sequence a(n) given integer n , see OEIS A174375.
function CW(n) return n^2 - BitwiseXor(n^2, n); end function;
// Fred Lunnon's mystery sequence, given integer u .
function FL(u)
local n; n := 0; while (CW(n)-u) ne 0 do n := n + (CW(n)-u); end while;
return n; end function;
FL(u) is constructed via Hensel lifting to solve equation CW(n)-u = 0 ,
observing that the 2-adic derivative exists and equals -1 .
Lemma (Ellingsen): for integer n and natural k ,
CW(n + 2^k) == CW(n) + 2^k (mod 2^(k+1)) .
This generalises inductively: for integer j ,
CW(n + 2^k j) == CW(n) + 2^k j (mod 2^(k+1)) .
Lemma: for natural k and integer n where n^2 < 2^k , there holds
CW(n + 2^k) = CW(n) - 2^k , exactly.
This generalises inductively to the right only: for natural j there holds
CW(n + 2^k j) = CW(n) + 2^k j ;
which fails for integer j < 0 (a non-Archimedean booby-trap!).
Lemma: CW(n) and FL(u) are well-defined;
the latter function termination an indirect consequence of the previous lemma.
Lemma: CW(n) and FL(u) are injective, via Ellingsen.
Theorem: CW(n) and FL(u) are inverse functions: for all integer n, u,
FL(CW(n) = n and CW(FL(u) = u .
Corollary: CW(n) and FL(u) permute the integers. ***
Fred Lunnon [29/05/23]
____________________
Function tables with columns respectively
[ n, CW(n), CW(-n), FL(n), FL(-n) ] for 0 <= n <= 64 ;
all presumptive candidates for OEIS!
[ 0 0 0 0 0]
[ 1 1 3 1 3]
[ 2 -2 10 6 2]
[ 3 -1 21 -1 5]
[ 4 -4 36 28 4]
[ 5 -3 55 13 7]
[ 6 2 70 58 14]
[ 7 -5 105 11 9]
[ 8 -8 136 120 8]
[ 9 -7 171 25 59]
[ 10 -10 210 -2 10]
[ 11 7 237 23 29]
[ 12 -12 300 20 12]
[ 13 5 335 21 15]
[ 14 -6 398 114 22]
[ 15 -13 465 51 17]
[ 16 -16 528 496 16]
[ 17 -15 595 49 19]
[ 18 -18 666 54 18]
[ 19 -17 741 47 245]
[ 20 12 788 236 52]
[ 21 13 871 -3 55]
[ 22 -14 982 42 30]
[ 23 11 1049 27 121]
[ 24 -24 1176 104 24]
[ 25 9 1243 1001 107]
[ 26 -26 1378 110 26]
[ 27 23 1437 39 237]
[ 28 4 1564 484 60]
[ 29 -11 1695 101 31]
[ 30 -22 1822 226 102]
[ 31 -29 1953 99 33]
[ 32 -32 2080 2016 32]
[ 33 -31 2211 97 35]
[ 34 -34 2346 38 34]
[ 35 -33 2485 95 37]
[ 36 -36 2628 -4 36]
[ 37 -35 2775 45 231]
[ 38 34 2854 218 46]
[ 39 27 3017 43 41]
[ 40 -40 3240 88 40]
[ 41 -39 3403 57 219]
[ 42 22 3506 222 1002]
[ 43 39 3661 119 61]
[ 44 -44 3916 244 44]
[ 45 37 4015 53 111]
[ 46 -38 4270 82 246]
[ 47 19 4401 83 497]
[ 48 -48 4656 464 48]
[ 49 17 4787 209 115]
[ 50 -50 5050 86 50]
[ 51 15 5189 79 85]
[ 52 -20 5428 204 84]
[ 53 45 5575 93 87]
[ 54 18 5814 74 62]
[ 55 -21 6073 -5 985]
[ 56 -56 6328 72 56]
[ 57 41 6459 73 459]
[ 58 6 6722 78 122]
[ 59 -9 6973 199 77]
[ 60 -28 7228 964 92]
[ 61 -43 7487 197 63]
[ 62 -54 7742 450 70]
[ 63 -61 8001 195 65]
[ 64 -64 8256 8128 64]
////////////////////////////////////////////////////////////////////////////////
More information about the SeqFan
mailing list