Informações
Transcrição
Informações
Proceeding Series of the Brazilian Society of Computational and Applied Mathematics Mini-simpósio: Códigos e reticulados algébricos Coordenador: Agnaldo José Ferrari 1 Introdução O CNMAC é o maior evento da SBMAC, congrega cerca de 800 participantes, entre pesquisadores, professores, profissionais de empresas e centros de pesquisas e estudantes das mais diversas áreas da Matemática Aplicada e Computacional. Constitui-se em uma oportunidade ı́mpar para discutir trabalhos em andamento, divulgar resultados e ficar a par da produção cientı́fica em desenvolvimento nas principais instituições nacionais. Esse evento acontece desde 1978. No CNMAC são apresentados Minicursos, Minissimpósios, Conferências, Sessões Técnicas de Comunicações, Sessões Especiais dedicadas à Iniciação Cientı́fica e ao Ensino, Exposições e Mesas Redondas. Também durante o CNMAC são premiados trabalhos de Iniciação Cientı́fica, dissertações de Mestrado e teses de Doutorado. O CNMAC tem como objetivo reunir a comunidade cientı́fica de Matemática Aplicada e Computacional, criando um fórum para o intercâmbio de idéias e surgimento de parcerias entre os participantes, assim como incentivando e inspirando a platéia de estudantes que comparecem ao evento. No ano de 2016 o Departamento de Matemática Aplicada da UFRGS de Porto Alegre - RS está empenhada em sediar o XXVII CNMAC, que será realizada no perı́odo de 05 a 09 de setembro. Em 2003, nesta linha, foi organizado o primeiro Mini-simpósio intitulado Empacotamento de esferas e códigos lineares dentro do XXVI CNMAC realizado no perı́odo de 08 a 11 de setembro no Ibilce - Unesp - São José do Rio Preto - SP. Em 2004, foi organizado o segundo Mini-simpósio intitulado Códigos e reticulados, dentro do XXVII CNMAC que foi realizado no perı́odo de 13 a 16 de setembro na PUC - Porto Alegre - RS, que teve como o objetivo de divulgar algumas técnicas utilizadas no estudo de códigos e reticulados, sobre anéis e corpos, enfocando o estudo de empacotamento de esferas em espaços euclidianos e hiperbólicos. Em 2016 estamos novamente engajados em organizar um Mini-simpósio intitulado Códigos e Reticulados algébricos dentro da programação do CNMAC2016 que será realizado em Gramado - RS no perı́odo de 05 a 09 de setembro, onde veremos deferentes métodos de pesquisar os melhores reticulados, visando sempre determinar aqueles de maior densidade de centro, através das técnicas geométricas e também das técnicas algébricas. No que tange aos códigos lineares corretores de erros serão explorados códigos sobre anéis finitos e também códigos obtidos via anéis de inteiros algébricos. Assim, o presente minisimpósio tem como objetivo de divulgar algumas técnicas utilizadas no estudo de reticulados algébricos obtidos via corpos de números, enfocando o estudo de de empacotamento de esferas em espaços euclidianos e hiperbólicos. Neste minisimpósio veremos, 2 também, deferentes métodos de pesquisar os melhores reticulados, visando sempre determinar aqueles de maior densidade de centro, através das técnicas geométricas e também das técnicas algébricas. 2 Programa - 06/09 (terça) e 07/09 (quarta) das 14 h às 16 h 1. 06/09 - 14:00 • Palestrante: Prof. Dr. Antonio Aparecido de Andrade • Tı́tulo: Construções de reticulados algébricos via corpos de números de condutor potência de primo. • Filiação: Departamento de Matemática - Ibilce - Unesp, São José do Rio Preto - SP 2. 14:30 • Palestrante: Prof. Dr. Agnaldo José Ferrari • Tı́tulo: Construção de reticulados inteiros via ideais em Z[x]/hf (x)i • Filiação: Departamento de Matemática, FC - Unesp, Bauru - SP 3. 15:00 • Palestrante: Profa. Dra. Grasiele Cristiane Jorge • Tı́tulo: Reticulados Dn -rotacionados via o composto de corpos • Filiação: Instituto de Ciência e Tecnologia - Unifesp, São José dos Campos SP 4. 15:30 • Palestrante: Profa. Dra. Carina Alves • Tı́tulo: Construção do reticulado de Leech baseada em teoria dos números algébricos • Filiação: Departamento de Matemática, Igce - Unesp, Rio Claro - SP 5. 07/09 - 14:00 • Palestrante: Profa. Dra. Cintya Wink de Oliveira Benedito • Tı́tulo: Reticulados algébricos via ordens maximais dos quatérnios • Filiação: Departamento de Matemática Aplicada, Imecc - Unicamp, Campinas - SP 6. 14:30 • Palestrante: Prof. Dr. Edson Donizete de Carvalho 3 • Tı́tulo: Códigos reticulados complexos provenientes de corpos de números • Filiação: Departamento de Matemática, Feis - Unesp, Ilha Solteira - SP 7. 15:00 • Palestrante: Profa. Dra. Sueli Irene Rodrigues Costa • Tı́tulo: Reticulados e códigos esféricos • Filiação: Departamento de Matemática, Imecc - Unicamp, Campinas - SP 8. 15:30 • Palestrante: Prof. Dr. Trajano Pires da Nóbrega Neto • Tı́tulo: Reticulados em extensões não ramificadas • Filiação: Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 3 Resumos das palestras A seguir apresentamos os resumos das palestras dos palestrantes financiados pelo FAPESP (Projeto Temático - 2013/25977-7)e que serão apresentadas no respectivo minisimpósio. 3.1 Patestra 1 Construções de reticulados algébricos via corpos de números de condutor potência de primo Antonio A. Andrade1 , Agnaldo J. Ferrari2 e Grasiele C. Jorge3 1 Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP 2 Departamento de Matemática, FC - Unesp, Bauru - SP 3 Instituto de Ciência e Tecnologia - Unifesp, São José dos Campos - SP [email protected], [email protected], [email protected] Agradecimentos a Fapesp - Processos 2013/25977-7 e 2014/14449-2 Seja Q ⊆ K uma extensão abeliana de corpos de grau n, ou seja, K é um corpo de números abeliano de grau n. Assim, o corpo K pode ser visto como um espaço vetorial de dimensão n sobre Q. Pelo Teorema de Kronecker-Weber, segue que existe um inteiro positivo n ∈ N tal que K ⊆ Q(ξn ), onde ξn é uma raiz n-ésima da unidade. Deste modo, existe um inteiro positivo n mı́nimo, chamado condutor, que satisfaça tal condição. Por Girald (1997) segue que o homomorfismo canônico do anel de inteiros de Q[θ], onde q et al. p √ θ = 2 + 2 + . . . + 2, pode ser utilizado para construir um reticulado Zn -rotacionado. Assim, nosso questionamento de como provar que tal corpo é o subcorpo maximal de um 2r -ésimo corpo ciclotômico L = Q(ξ), onde ξ = ξ2r é uma raiz pr -ésima primitiva da unidade e r > 1 é um inteiro positivo, uma vez que não existe um método que descreva a estrutura dos subcorpos K de Q(ξ2r ), exceto quando K é o subcorpo maximal. Sejam 4 ξ = ξn , onde n = 2, 4, pr , 2pr , L = Q(ξ) e G = Gal(L : Q). O anel de inteiros algébricos OK , onde K ⊆ L é conhecido para os corpos quadráticos, ciclotômicos e corpos maximais reais. Assim, explorando o fato de G ser um grupo cı́clico, logo abeliano, o objetivo é encontrar subcorpos de L juntamente com seu anel de inteiros algébricos. Fazendo uso desses corpos, nesse trabalho apresentamos resultados de construções de reticulados algébricos com boa distância produto mı́nima. Referências [1] L.C. Washington, Introduction to ciclotomic fields, Springer-Verlag, New York, 1982. [2] P. Samuel, Algebraic theory of numbers, Hermann, Paris, 1970. [3] P. Ribenboin, Classical theory of algebraic numbers, Springer Verlag, New York, 2001. [4] Giraud, X., Boutilon, E., Belfiore, J. C., Algebraic tools to build modulation schemes for fading channels, IEEE Transacions on Information Theory, 43(2) (1997) 938-952. 3.2 Palestra 2 Construção de reticulados inteiros via ideais em Z[x]/hf (x)i Agnaldo José Ferrari1 e Antonio Aparecido de Andrade2 1 Departamento de Matemática, FC - Unesp, Bauru - SP 2 Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP [email protected], [email protected] Agradecimentos a Fapesp - Processos 2013/25977-7 e 2014/14449-2 Neste trabalho apresentamos a construção dos reticulados densos [6] em dimensão 2 a 8 através de uma nova abordagem, via ideais reticulados. Tais ideais aparecem na Ciência da Computação na construção das chamadas funções de Hash, quando do estudo de uma criptografia baseada em reticulados [3]. A segurança desse tipo de esquema criptográfico baseia-se em um certo problema que aparece para uma particular classe de reticulados, os reticulados cı́clicos. No entanto, nossa ênfase será adaptar a técnica utilizada na criptografia para construir reticulados densos. Uma outra importante aplicação dos reticulados está relacionada à Teoria da Informação, mais especificamente à Teoria dos Códigos Corretores de Erros [4]. Consideramos o anel quociente Z[x]/hf (x)i, em que f (x) é um polinômio mônico de grau n em Z[x]. Se I = hg1 (x), g2 (x), · · · , gm (x)i é um ideal em Z[x]/hf (x)i, então o conjunto I é gerado por g1 (x), g1 (x)x, · · · , g1 (x)xn−1 , · · · , gm (x), gm (x)x, · · · , gm (x)xn−1 e pela Forma Normal de Hermite [1], existe um conjunto de no máximo n vetores linearmente independentes de I que formam uma base para I. Assim, I é um reticulado inteiro de dimensão n. Podemos dizer que um vetor v = (v0 , v1 , · · · , vn−1 ) ∈ Zn corresponde a um polinômio w = w0 + w1 x + · · · + wn−1 xn−1 ∈ Z[x]/hf i se para todo i, vi = wi . Reciprocamente, um reticulado Λ corresponde a um ideal I se todo vetor (v0 , v1 , · · · , vn−1 ) ∈ Λ se, e somente 5 se, o polinômio v0 + v1 x + · · · + vn−1 xn−1 ∈ I. Desse modo, um ideal reticulado é um reticulado que corresponde a um ideal em algum anel especı́fico Z[x]/hf (x)i. Uma importante caracterı́stica dos ideais reticulados em Z[x]/hf (x)i, para f (x) irredutı́vel, é que possuem posto completo [3]. Neste trabalho discutimos também alguns parâmetros importantes acerca dos ideais reticulados, tais como distância mı́nima e densidade de empacotamento. Referências [1] H. Cohen, A course in computational algebraic number theory, Springer, 1996. [2] J. H. Conway, N. J. A. Sloane, Sphere packings, Lattices and Groups, 3rd edition, Spring-Verlag, New York, 1999. [3] V. Lyubashevsky, Towards pratical lattice-based cryptography, Tese de Doutorado, University of California, San Diego, 2008. [4] C. Shannon, Mathematical theory of communication, Bell Systems Technical Journal, 27 (1948) pt. 1: 379-423; pt. 2: 623-656. 3.3 Palestra 3 Reticulados Dn -rotacionados via o composto de corpos Grasiele Cristiane Jorge1 e Antonio Aparecido de Andrade2 de Ciência e Tecnologia - Unifesp, São José dos Campos - SP 2 Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP [email protected], [email protected] Agradecimentos a Fapesp - Processo 2013/25977-7 1 Instituto Um reticulado Λ ⊆ Rn é um subgrupo aditivo discreto do Rn gerado por combinações lineares inteiras de n vetores linearmente independentes {v1 , · · · , vn } ∈ Rn , isto é, Λ = Pn { i=1 ai vi : ai ∈ Z, para todo i = 1, 2, · · · , n}. Constelações de sinais tendo estrutura de reticulado têm sido utilizadas como suporte para transmissão de sinais. Neste trabalho, utilizando teoria algébrica dos números, apresentamos um método para construir uma famı́lia de reticulados Dn -rotacionados em Rn que são adequados para serem utilizados sobre os canais com desvanecimento do tipo Rayleigh. Reticulados bons para estes canais são reticulados com diversidade máxima e alta distância produto mı́nima [3]. Sejam K um corpo de números de grau n, OK seu anel de inteiros e α ∈ OK um elemento totalmente real e positivo. Em [1,2] foi introduzido um homomorfismo σα : K → Rn tal que se I ⊆ OK é um Z-módulo livre de posto n, então σα (I) é um reticulado em Rn e foi mostrado que se K é um corpo de números totalmente real, então σα (I) é um reticulado com diversidade máxima. Algumas construções de reticulados Dn -rotacionados com diversidade máxima foram apresentadas em [4, 5] via os corpos Q(ζp + ζp−1 ), p ≥ 7 primo e Q(ζ2r + ζ2−1 r ), r ≥ 4. Em nossa construção, utilizamos subcorpos K ⊆ Q(ζp + ζp−1 ), p ≥ 13 primo, −1 r com [K : Q] = p−1 4 e através do composto K Q(ζ2 + ζ2r ) foi possı́vel obter famı́lias de reticulados Dn -rotacionados com diversidade máxima. Em cada caso a distância produto mı́nima foi obtida. 6 Referências [1] E. Bayer-Fluckiger, Lattices and number fields, Contemporary Mathematics, 241 (1999) 69-84. [2] E. Bayer-Fluckiger, Ideal lattices, Proceedings of the conference Number theory and diophantine geometry, Zurich, 1999, Cambridge Univ. Press, 168-184, 2002. [3] E. Bayer-Fluckiger, F. Oggier, E. Viterbo, New algebraic constructions of rotated Zn -lattice constellations for the rayleigh fading channel, IEEE Transactions on Information Theory, 50(4) (2004) 702-714. [4] G.C. Jorge, A.J. Ferrari, S.I.R. Costa, Rotated Dn -lattices, Journal of Number Theory, 132 (2012) 2397-2406. [5] G. C. Jorge, S. I. R. Costa, On rotated Dn -lattices constructed via totally real number fields, Archiv der Mathematik, 100 (2013) 323-332. 3.4 Palestra 4 Construção do reticulado de Leech baseada em teoria dos números algébricos Carina Alves1 e Jean-Claude Belfiore2 1 Departamento de Matemática, Igce - Unesp, Rio Claro - SP 2 TELECOM - Paris Tech, Paris, França [email protected], [email protected] A teoria dos números algébricos tem sido utilizada no desenvolvimento de códigos corretores de erros e mais recentemente na teoria de reticulados. Ela tem sido uma importante ferramenta que permite projetar bons códigos para canais com desvanecimento e além disso, constelações de sinais provenientes de reticulados com boa densidade de empacotamento tem bom desempenho sobre o canal gaussiano [2]. Reticulados podem ser construı́dos via um corpo de números K, considerando a representação geométrica de ideais no anel dos inteiros de K, OK . Craig, em [1], mostrou que os reticulados D4 , E8 , K12 , Λ16 e Λ24 podem ser obtidos a partir de ideais devidamente escolhidos no anel dos inteiros de corpos ciclotômicos. A vantagem de obter reticulados por este método é que podemos identificar os pontos do reticulado no Rn como elementos de um corpo de números, e portanto, é possı́vel utilizar algumas propriedades do corpo no estudo de tais reticulados. Em [3] o reticulado de Leech, Λ24 ,√foi construı́do usando o produto tensorial de dois reticulados sobre Z[α], onde α = (1 + −7)/2, e que quando vistos como um Z-reticulado, são equivalentes ao reticulado E8 e ao reticulado de Barnes Pb . Neste trabalho fazemos o uso da teoria dos números algébricos para construir infinitos reticulados algébricos equivalentes ao reticulado Λ24 . 7 Referências [1] M. Craig, Extreme forms and cyclotomic, Mathematicka, 25 (1978b) 44-56. [2] J, Boutros, E. Viterbo, C. Rastello, J-C. Belfiore, Good lattice constellation for both rayleigh fading and gaussian channels, IEE Trans. on Inform. Theory, 42 (1996) 502518. [3] G. Nebe, An even unimodular 72-dimensional lattice of minimum, Journal für die reine und angewandte Mathematik, 673 (2012) 237-247. 3.5 Palestra 5 Reticulados algébricos via ordens maximais dos quatérnios Cintya Wink O. Benedito1 , Sueli I. R. Costa2 e Carina Alves3 de Matemática Aplicada, Imecc - Unicamp, Campinas - SP 2 Departamento de Matemática, Imecc - Unicamp, Campinas - SP 3 Departamento de Matemática, Igce - Unesp, Rio Claro - SP [email protected], [email protected], [email protected] 1 Departamento Neste trabalho temos como objetivo apresentar uma construção de reticulados algébricos utilizando ordens maximais de uma álgebra dos quatérnios definida sobre um corpo de números totalmente real. Tais reticulados são identificados através de sua matriz de Gram e de sua matriz geradora. Com esta construção é possı́vel obter reticulados rotacionados de dimensões múltiplas de 4 com densidade de centro ótima. Além da densidade de centro, pretendemos analisar outros parâmetros importantes para que os reticulados obtidos através desta construção possam ser utilizados em canais gaussianos, do tipo Rayleigh com desvanecimento e MIMO (multiple-input and multiple-output). Referências [1] E. Bayer-Fluckiger, Lattices and number fields, Contemporary Mathematics, 241 (1999) 69-84. [2] F.-T. Tu and Y. Yang, Lattice packing from quaternion algebras, RIMS Kb okyb uroku Bessatsu, (2012) 229-237. [3] C. Alves and J,-C. Belfiore, Lattices from maximal orders into quaternion algebras, J. Pure Appl. Algebra, 219(4) (2015) 687-702. [4] I. Reiner, Maximal Orders, Academic Press, London, 1975. [5] C. Maclachlan and A. W. Reid, The arithmetic of hyperbolic 3-manifolds, SpringerVerlag, New York, 2003. [6] J.H. Conway and N.J.A. Sloane, Sphere Packings, lattices and groups, SpringerVerlag, 1998. 8 3.6 Palestra 6 Códigos reticulados complexos provenientes de corpos de números Edson Donizete de Carvalho Departamento de Matemática, Feis - Unesp, Ilha Solteira - SP [email protected] Códigos reticulados são obtidos por meio da Construção A, um método prático de se obter reticulados Λ em CN (o espaço Euclidiano complexo de dimensão N ), tais reticulados são recobertos por meio de convenientes translações de um código linear Euclidiano complexo C, isto é, o código C pode ser visto como uma partição do reticulado Λ em CN . Na literatura, estes reticulados também são conhecidos por reticulados cúbicos, em razão da região fundamental destes reticulados terem um formato geométrico de um hipercubo em CN . A menos de isomorfismos os reticulados cúbicos são versões escalonadas de reticulados do tipo cZ2N ou cAN 2 , onde A2 denota o reticulado hexagonal. A busca por bons parâmetros para diversos problemas envolvendo codificação de canal, tais como a energia média de uma constelações de sinais, ganho de diversidade, quantização de canal dentre outros estão intimamente relacionados ao processo de construção e geração de versões escalonadas de reticulados e na maneiras de particionar tais reticulados, o que leva a geração dos códigos reticulados complexos. Mostraremos o quanto a teoria algébrica dos números é rica em propriedades algébricas, possibilitando a geração e a partição de reticulados cúbicos Z2N ou AN 2 de forma eficiente, por meio de ferramentas algébricas provenientes de extensões ciclı́cas de corpos de números do tipo E/F , onde F = Q(i) ou Q(ζ3 ), onde i e ζ3 denotam a raı́z quarta e terceira da unidade, respectivamente. Referências [1] M. Craig, Extreme forms and cyclotomic, Mathematicka, 25 (1978b) 44-56. [2] J, Boutros, E. Viterbo, C. Rastello, J-C. Belfiore, Good lattice constellation for both rayleigh fading and gaussian channels, IEE Trans. on Inform. Theory, 42 (1996) 502518. [3] G. Nebe, An even unimodular 72-dimensional lattice of minimum, Journal für die reine und angewandte Mathematik, 673 (2012) 237-247. 9 3.7 Palestra 7 Reticulados e códigos esféricos Sueli I. R. Costa Departamento de Matemática, Imecc - Unicamp, Campinas - SP [email protected] Agradecimentos a Fapesp - Processo 2013/25977-7. Distribuições de pontos sobre uma esfera n-dimensional utilizadas em comunicação sobre canais gaussianos são uma generalização dos sinais PSK (phase shift keyed signal sets) a dimensões maiores que dois. Além de maximizar densidade de empacotamento, outras considerações práticas, como armazenamento e facilidade de decodificação são muito importantes. Códigos esféricos dados por órbitas de vetores sob a ação de grupos comutativos de matrizes ortogonais foram introduzidos por D. Slepian [1] e tem recebido especial atenção devido à simetria e homogeneidade que decorrem de sua estrutura algébrica. Para esferas em dimensão para estes códigos se localizam em toros planares e podem serem caracterizados como quocientes de reticulados na metade da dimensão. Limitantes para a densidade destes reticulados podem serem associados à densidade destes reticulados. A folheação de uma esfera em dimensão par pode ser utilizada na construção de bons códigos esféricos discretos (códigos de grupos quase-comutativos) e também curvas para a transmissão de fontes contı́nuas sobre canais. Em ambos os casos a performance do código está relacionada a densidade dos reticulados especı́ficos e a famı́lias dos sub-reticulados ortogonais destes. No caso contı́nuo a densidade de empacotamento das curvas leva à procura de reticulados-projeção com boa densidade de empacotamento. Neste trabalho, baseada in diversos trabalhos como os abaixo listados, abordamos o estado atual de desenvolvimento deste tema, bem como resultados recentes, pesquisas em andamento e perspectivas. Referências [1] A. Campello, C. Torezzan, S.I.R. Costa, Constructive spherical codes on layers of flat tori, IEEE Trans. Inf. Theory, 59(10) (2013) 6644?6654. [2] S. I. R. Costa, C. Torezzan, A. Campello, and V. A. Vaishampayan, Flat tori, lattices and spherical codes, Proc..IEEE Inf. Theory and Appl. Workshop, (2013) 471-479. [3] G.D. Forney Jr., Geometrically uniform codes, IEEE Trans. Inform. Theory, 37(5) (1991) 1241?1260. [4] D. Slepian, Group codes for the Gaussian channel, Bell Syst. Tech. J., 47 (1968) 575-602. [5] N. J. A. Sloane, V. A. Vaishampayan and S. I. R. Costa, A note on projecting the cubic lattice, Discrete and Computational Geometry, 46(3) (2011) 472?478. [6] C. Torezzan, S.I.R. Costa and V. A. Vaishampayan, Constructive spherical codes on layers of flat tori, IEEE Trans. Inf. Theory, 59(10) (2013) 6655?6672. 10 [7] V.A.Vaishampayan and S.I.R.Costa, Curves on sphere, shift-map dynamics and error control for continuous alphabet sources, IEEE Trans. Inf. Theory, 49(7) (2003) 16581672. 3.8 Palestra 8 Reticulados em extensões não ramificadas Trajano Pires da Nóbrega Neto Departamento de Matemática, Ibilce - Unesp, São José do Rio Preto - SP [email protected] Um empacotamento reticulado é um empacotamento em que o conjunto dos centros das esferas formam um reticulado no Rn . O problema clássico do empacotamento esférico consiste em encontrar um arranjo de esferas idênticas no espaço euclidiano de modo que a fração do espaço coberto pelas esferas seja a maior possı́vel. Este fato é uma versão do 18o Problema de Hilbert - 1900. Usando técnicas diversas tem-se obitido soluções parciais. Um dos métodos que apresenta boas caracterı́sticas é através do homomorfismo canônico (ou Minkowski). Nesse trabalho, apresentamos um método de construção de reticulados, obtidos via representação geométrica de módulos contidos nos anéis de inteiros algébricos de corpos de números, onde tais corpos são partes de uma torre de extensões não ramificadas de um corpo de números pré-fixado. Referências [1] M. Craig, Extreme forms and cyclotomic, Mathematicka, 25 (1978b) 44-56. [2] L.C. Washington, Introduction to ciclotomic fields, Springer-Verlag, New York, 1982. [3] P. Samuel, Algebraic theory of numbers, Hermann, Paris, 1970. [4] P. Ribenboin, Classical theory of algebraic numbers, Springer Verlag, New York, 2001.