Taxa de crescimento exponencial do número de permutações polinomiais

Abstract

Resulta que um conjunto de 4 polinômios distintos que passam pela origem, induzem de forma ?natural? uma permutação de 4 elementos. A forma ?natural? consiste em analisar a configuração local dos gráficos dos polinômios em torno da origem e ordená-los de acordo com a posição que ocupam à esquerda do zero e reordená-los de acordo com a sua posição à direita do zero. Neste trabalho estudamos o problema enunciado por Maxim Kontsevich que consiste em saber se, a permutação (2, 4, 1, 3) pode ser induzida por um conjunto de 4 polinômios. Permutações induzidas por polinômios são chamadas permutações polinomiais. Mostramos uma caracterização mais geral, devido a Étienne Ghys, que afirma que nenhuma permutação de n elementos que contenha (2, 4, 1, 3) pode ser induzida por polinômios. Também contamos o número de permutações polinomiais de n elementos e analisamos sua taxa de crescimento. Tal contagem é feita transportando o problema de polinômios a um problema de árvores planares.

Abstract: It turns out that a set with 4 different polynomials passing through the origin ?naturally? induce a permutation of 4 elements. The ?natural? way consists of analyzing the local configuration of the polynomials? graphs and ordering them according to the position they occupy to the left and right of zero. In this work we study the problem due to Maxim Kontsevich which consists in knowing whether the permutation (2, 4, 1, 3) can be induced by a set of 4 polynomials. Permutations induced by polynomials are called polynomial permutations. We show a more general characterization, due to Étienne Ghys, who states that no permutation of n elements containing (2, 4, 1, 3) can be induced by polynomials. We also count the number of polynomial permutations of n elements and analyze their growth rate. Such counting is done by transporting the polynomial problem to a planar tree problem.