Cantor's polynomials.
Bijections from Nn to N.

Coding of Nn by elements of N

The two only polynomials of degree 2, of the two variables x and y, which are bijections of N2 on N, are the polynomials of Cantor (Cantor 1873. Shown in 1923 by Fueter and Pólya):

f(x,y)=((x+y)^2+3x+y)/2 et g(x,y)=((x+y)^2+x+3y)/2.

Naturally g(x,y)=f(y,x)

The general problem which is to determine the polynomials of degrees d bijective of Nn on N remains open and seems very difficult.

By composing the preceding polynomials one obtains bijections of Nn on N.

For example, the polynomials f(f(x, y), z), f(f(f(x, y), z), t) define bijections of N3 on N and N4 on N, but there are many others of them.

Values

The table below gives some values of the polynomial: f(x,y)=((x+y)^2+3x+y)/2.






Calculations

Bijection from N2 to N

Starting from the couple (x, y) we can calculate his image k = f(x, y) in N.
Conversely, starting from k, we can calculate x and y tels que f(x, y) = k.


x :  y :  f(x,y) : 
   

Bijection from Nn to N

By composing n-1 time the bijection above of N2 on N one obtains a bijection of Nn on N.

For example f3(x, y, z) = f(f(x, y), z) ou encore f4(x, y, z, t) = f(f(f(x, y), z), t)


x y z t ... :  n :  fn(x,y,...) : 
   

Decimation and bijection from N2 to N

(See Éric Angelini's Decimation-like sequences).

Greedy algorithm for fn(x, y):

Choose a step n>1.
In the half line N = {0, 1, 2, 3, 4, 5, 6 ...}, in free cases, from n places to n places (the step is n) and in the case K write fn(0,y)= K (and K is no longer free). Then repeat the process for fn(1,y), for fn(,y) and so on.


n =     x y =        



This functions fn permit to define integer Sequences :
Sequences fn(x, 0) when x grows
f2(x, 0) : 0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,... OEIS A000225
f3(x, 0) : 0,1,2,4,7,11,17,26,40,61,92,139,209,314,472,709,1064,1597,2396,3595,5393,8090,12136,18205,27308,40963,61445,... OEIS A006999
f4(x, 0) : 0,1,2,3,5,7,10,14,19,26,35,47,63,85,114,153,205,274,366,489,653,871,1162,1550,2067,2757,3677,4903,6538,8718,...
f5(x, 0) : 0,1,2,3,4,6,8,11,14,18,23,29,37,47,59,74,93,117,147,184,231,289,362,453,567,709,887,1109,1387,1734,2168,2711,3389,...
Sequences fn(x, 1)
f2(x, 1) : 2,5,11,23,47,95,191,383,767,1535,3071,6143,12287,24575,49151,98303,...OEIS A055010 et A083329 (sauf le premier terme) 
f3(x, 1) : 3,5,8,13,20,31,47,71,107,161,242,364,547,821,1232,1849,2774,4162,6244,9367,14051,21077,31616,47425,71138,...
f4(x, 1) : 4,6,9,13,18,25,34,46,62,83,111,149,199,266,355,474,633,845,1127,1503,2005,2674,3566,4755,6341,8455,11274,...
Sequences fn(x, x)
f2(x, x) : 0,5,19,55,143,351,831,1919,4351,9727,21503,47103,...
f3(x, x) : 0,5,16,34,67,121,223,382,655,1091,1840,2977,4858,7834,12775,20290,32663,51421,82484,...
f4(x, x) : 0,6,15,31,55,90,147,223,338,509,745,1077,1589,2274,3239,4671,6557,9255,13149,18467,...
Sequences fn(1, y) y growing
f2(1, y) : 1,5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,...OEIS A016813
f3(1, y) : 1,5,10,14,19,23,28,32,37,41,46,50,55,59,64,68,73,77,82,86,91,95,100,104,109,113,118,...
f4(1, y) : 1,6,11,17,22,27,33,38,43,49,54,59,65,70,75,81,86,91,97,102,107,113,118,123,129,134,139,145,150,155,161,166,171,177,182,187,193,...
Sequences fn(2, y)
f2(2, y) : 3,11,19,27,35,43,51,59,67,75,83,91,99,107,115,123,...OEIS A017101 8y+3
f3(2, y) : 2,8,16,22,29,35,43,49,56,62,70,76,83,89,97,103,110,116,124,130,137,143,151,157,164,170,178,...
f4(2, y) : 2,9,15,23,30,37,45,51,58,66,73,79,87,94,101,109,115,122,130,137,143,151,158,165,173,179,186,194,201,207,215,222,229,237,243,250,258,...

Site links

See the link pages on Cantor and combinatorics.

Other links

Some remarks on the Cantor pairing function Meri Lisi – "Le Matematiche" Vol. 62 no 1 p. 55-65 (2007) – In this paper, some results and generalizations about the Cantor pairing function are given. In particular, it is investigated a very compact expression for the n-degree generalized Cantor pairing function.
On n-tupling polynomials of small degrees" Maxim Vsemirnov, (Programme of the 14th Days of Weak Arithmetics St.Petersburg, Russia May 22-24, 1997). (The first page only).
Georg Cantor (1845-1918): the man who tamed infinity Eric Schechter. (Slides for a lecture about infinity).
Cantor Georg Ferdinand russe, 1845-1918 ChronoMath, une chronologie des MATHEMATIQUES. Dénombrabilité de Q
Georg CANTOR (1845 - 1918)


















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014