Rigo a Rigo Juli´ Juli´ an n Osorio Osorio Diego Diego Fernando Fernando Ruiz Ruiz Carlos Alberto Trujillo Cristhian Leonardo Carlos Alberto Trujillo Cristhian Leonardo Urbano Urbano Universidad del Cauca Universidad del Cauca Recibido: octubre 23, 2013

1

Aceptado: agosto 20, 2014

Recibido: octubre 23, 2013 Aceptado: agosto DE 20, 2014 SECUENCIAS SONAR Y CONJUNTOS SIDON

Facultad de Ciencias Naturales y Exactas Resumen Resumen Universidad delconmutativo Valle A es un conjunto de Sidon en un grupo G notado aditivamente si A es un conjunto de Sidon en un grupo conmutativo G notado aditivamente si el n´ umero de representaciones de todo elemento no identidad de G como diferencia el n´ umero de representaciones de todo elemento no identidad de G como diferencia de dos elementos de A es a lo sumo 1. Una secuencia sonar m × n es una funci´ on de dos elementos de A es a lo sumo 1. Una secuencia sonar m × n es una funci´ on f : {1, . . . , n} → {1, . . . , m} tal que su grafo asociado Gf := {(x, f (x)) : 1 ≤ x ≤ n} f : {1, . . . , n} → {1, . . . , m} tal que su grafo asociado Gf := {(x, f (x)) : 1 ≤ x ≤ n} es un conjunto de Sidon en el grupo Z × Z. Si G(m) denota el m´ aximo entero positivo es un conjunto de Sidon en el grupo Z × Z. Si G(m) denota el m´ aximo entero positivo Sonar Sequences and Sidon Sets Rigo Juli´ a n Osorio n tal que existe una secuencia sonar Diego m × n, Fernando utilizando elRuiz concepto de energ´ıa aditiva n tal que existe una secuencia sonar m × n, utilizando el concepto de energ´ıa aditiva Carlos Alberto Trujillo Cristhian Leonardo Urbano y algunas de sus propiedades elementales. En este trabajo se prueba que G(m) ≤ y algunas de sus propiedades elementales. En este trabajo se prueba que G(m) ≤ 1/3 m + 3,78m2/3 4,76m 2. Adem´ as, utilizando la construcci´ on de conjuntos de Sidon Rigo Julián Diego Fernando Ruiz 2/3 + 1/3 +Osorio m + 3,78m + 4,76m + 2. Adem´ as, utilizando la construcci´ on de conjuntos de Sidon Universidad del Cauca tipo Bose enCarlos Z 2 Alberto se construyen secuencias sonarCristhian (q − 1) × q, para toda potencia prima Trujillo Leonardo Urbano tipo Bose en Zqq2 −1 −1 se construyen secuencias sonar (q − 1) × q, para toda potencia prima q. Universidad del Cauca q. 11 Recibido: octubre 23, 2013 Aceptado: agosto 20, 2014 Received: October 23, 2013 Accepted: 3, 2014 Palabras Clave: Conjuntos de Sidon, secuencias sonar,February energ´ıa aditiva. Palabras Clave: Conjuntos de Sidon, secuencias sonar, energ´ıa aditiva. Resumen SONAR DE SIDON SECUENCIAS SONAR YCONJUNTOS CONJUNTOS DE SIDON Pag. 33-42 A es SECUENCIAS un conjunto de Sidon en un Y grupo conmutativo G notado aditivamente si Abstract Abstract el n´ u mero de representaciones de todo elemento no identidad de G como diferencia A is a Sidon set in an additive commutative group G if the number of representations A iselementos a Sidon setdein A an es additive commutative group G if sonar the number representations de each dos a lo secuencia m × nof funci´ on of non-identity element in sumo G, as 1.a Una difference of two elements inesAuna is at most of each non-identity element in G, as a difference of two elements in A is at most f :An {1,m . . .×, n} → {1,sequence . . . , m} tal su grafof asociado := {(x, 1 ≤ that x ≤ n} 1. n sonar is que a function : {1, . . . , G n}f → {1, . .f.(x)) , m} : such its 1. An m × n sonar sequence is a function fSi :G(m) {1, . . denota . , n} →el{1, .ximo . . , m}entero such positivo that its es un conjunto de Sidon en el grupo Z × Z. m´ a associated graph Gf := {(x, f (x)) : 1 ≤ x ≤ n} is a Sidon set in the group Z × Z. associated graph una Gf secuencia := {(x, f (x)) : 1m≤× xn, ≤utilizando n} is a Sidon set in de theenerg´ group Z × Z. n tal quedenotes existe sonar concepto ıa naditiva If G(m) the maximum positive integer such thatel there exists an m× sonar If G(m) denotes the maximum positive integer such that there exists an m × n sonar y algunas using de sus propiedades elementales, en properties. este trabajo se prueba que G(m) ≤ sequence, additive energy and some of its In this paper, we show that 2/3 1/3 sequence, using additive energy and some of its properties. In this paper, we show that Rigo Juli´ a n Osorio Diego Fernando Ruiz Rigo Juli´ a n Osorio Diego Fernando Ruiz m + 3,78m + 4,76m + 2. Adem´ as, utilizando la construcci´ on de conjuntos de Sidon 2/3 1/3 G(m) ≤ m + 3,78m 2/3 + 4,76m1/3 + 2. Furthermore, using the construction of Sidon sets G(m) ≤ men + 3,78m + 4,76mTrujillo + 2. Furthermore, using the construction of Sidon sets Carlos Alberto Cristhian Leonardo Urbano Carlos Alberto Trujillo Cristhian Leonardo Urbano tipo Bose Z construyen secuencias sonar (q − 1) × q, para toda 2 −1 se q type Bose in Zq2 −1 we construct (q − 1) × q sonar sequences for all primepotencia power q.prima type Bose in Z we construct (q − 1) × q sonar sequences for all prime power q. 2 q −1 q.

SECUEN

Rigo Jul Carlos A

Universidad Universidaddel delCauca Cauca

Keywords: Sidon sets, sonar sequences, additive energy. Keywords: Sidon Conjuntos sets, sonarde sequences, additive energy. Recibi Palabras Clave: Sidon, secuencias sonar, energ´ıa aditiva. Recibido: Recibido: octubre octubre23, 23,2013 2013 Aceptado: Aceptado:agosto agosto20, 20,2014 2014 Secuencias sonar y conjuntos de Sidon Resumen Abstract 1. Introducci´ o n 1. Resumen Introducci´ on Resumen A is a Sidon set in an additive commutative group G if the number of representations A es un conjunto A es un conjunto de en un grupo conmutativo GGnotado si1. eselement un ıa conjunto de Sidon Sidon enas unauno grupo conmutativo notado si el n´ umero de represen En teor´ de n´ u aditiva, de que ha gran of each non-identity G difference ofproblemas two elements in aditivamente Aaditivamente istenido at most En teor´ ıarepresentaciones de n´ umeros meros in aditiva, uno de los los problemas que ha tenido gran el n´ u mero de de todo elemento no identidad de G como diferencia mero de representaciones de todo elemento no identidad de G como diferencia de dos elementos de impacto en el a ´ rea de las telecomunicaciones de los conjuntos de Sidon, el An m × n sonar sequence is a function f : {1,es . . .el , n} → {1, . . . , m} such that its impacto en el a ´ rea de las telecomunicaciones es el de los conjuntos de Sidon, el de dos elementos de aanombre lo sumo Una sonar m funci´ onlos elementos de A A es es sumo Una secuencia sonarset m×in ×n the nes esuna una funci´ oZ. fn : {1, . . . , n} → {1, . cual data desde 1930. en Simon Sidon quien associated graph G {(x, flo(x)) : es 11.1. ≤ xhonor ≤secuencia n} al a Sidon group Z× f := Su cual data desde 1930. Su nombre es en honor alis analista analista Simon Sidon quien los fintrodujo : {1, . . . , n} → {1, . . . , m} tal que su grafo asociado G := {(x, f (x)) : 1 ≤ x ≤ n} . . , n} → {1, . . . , m} tal que su grafo asociado G := {(x, f (x)) : 1 ≤ x ≤ n} es un conjunto de Sido f f con el prop´ o sito de resolver problema en an´ aalisis arm´ ooan nico [1]. If G(m) denotes the maximum positive un integer such that there exists m× n Sidon sonar introdujo con el prop´ o sito de resolver un problema en an´ lisis arm´ nico [1]. Sidon es un conjunto de Sidon en el grupo Z × Z. Si G(m) denota el m´ a ximo entero positivo conjunto de Sidonde enenteros el grupo Z × Z. G(m) denotainelthis m´ aximo entero positivo n tal que existe una s investigaba conjuntos con la que las sumas de dos sequence, using additive energy andpositivos some of Si its properties, we show that investigaba conjuntos de enteros positivos con la propiedad propiedad quepaper las sumas de dos n tal que existe una secuencia sonar m × n, utilizando el concepto de energ´ ıa aditiva 2/3 1/3 que existe una secuencia sonar m × n, utilizando el concepto de energ´ ıa aditiva y algunas de sus pro G(m) ≤ m + 3,78m + 4,76m + 2. Furthermore, using the construction of Sidon sets ydue algunas de sus propiedades elementales. En este trabajo se prueba que G(m) ≤ algunas de sus propiedades elementales. En este trabajo se prueba que G(m) ≤ m + 3,78m2/3 + 4,76m to Bose in Z 2 −1 we construct (q − 1) × q sonar sequences for all prime power q. q 2/3 1/3 m + 3,78m + + aas,s,utilizando onondedeconjuntos Sidon 3,78m2/3 +4,76m 4,76m1/3 +2.2.Adem´ Adem´ utilizandolalaconstrucci´ construcci´ conjuntosdede Sidon tipo Bose en Zq2 −1 se tipo Bose en Z se construyen secuencias sonar (q − 1) × q, para toda potencia prima Bose en Z se construyen secuencias sonar (q − 1) × q, para toda potencia prima q. 2 2 qq −1 −1 sets, sonar sequences, additive energy. Keywords: Sidon q. Palabras clave: Conjuntos de Sidon, secuencias sonar, energía aditiva. Palabras Clave: Con Palabras Clave: Conjuntos de Sidon, secuencias sonar, energ´ ıa aditiva. Palabras Clave: Conjuntos de Sidon, secuencias sonar, energ´ ıa aditiva. 1. Introducci´ on 1 Introducción Abstract En teor´ıa de n´ umeros aditiva, uno de los problemas que ha tenido gran A is a Sidon set in Abstract Abstract impacto el ´aset reain telecomunicaciones es G elGifde los conjuntos de Sidon, el A is Sidon an additive commutative number ofofrepresentations is aaen Sidon set inde anlas additive commutativegroup group ifthe the number representations of each non-identity e cual data desde 1930. Su nombre es aen honor alofof analista SimoninSidon quien los of each non-identity element in two non-identity element in G, G, as as a difference difference twoelements elements inAAis isat atmost most 1. An m × n sonar se introdujo con el prop´ o sito de resolver un problema en an´ a lisis arm´ o nico [1]. Sidon 1. An m . ....,.m} m× × nn sonar sonar sequence sequence isis aa function functionff : :{1, {1,. . .. ,. n} , n}→→{1, {1, , m}such suchthat thatitsits associated graph Gf : investigabagraph conjuntos enteros con que las sumas dos associated G {(x, ff(x)) n} isisapropiedad ininthe ×× Z. associated graph Gff := :=de {(x, (x)) :positivos : 11 ≤≤ xx≤≤ n}la aSidon Sidonset set thegroup groupZ de Z Z. If G(m) denotes the m If G(m) denotes ×× n nsonar denotes the the maximum maximum positive positiveinteger integersuch suchthat thatthere thereexists existsananmm sonar sequence, using additiv 2/3 sequence, using additive energy sequence, using additive energyand andsome someofofits itsproperties. properties.InInthis thispaper, paper,weweshow showthat that agosto 2014 Volumen 18 No. 1, 33G(m) ≤ m + 3,78m 2/3 1/3 2/3 1/3 G(m) ≤ m sets m+ +3,78m 3,78m + +4,76m 4,76m ++2.2.Furthermore, Furthermore,using usingthe theconstruction constructionofofSidon Sidon sets type Bose in Zq2 −1 we type Bose Bose in in Z Zqq22−1 we construct construct(q(q−−1)1)××qqsonar sonarsequences sequencesfor forallallprime primepower powerq. q. −1 we Keywords: Sidon sets

Revista de Ciencias

R. J. Osorio, D. F. Ruiz, C. A. Trujillo y C. L. Urbano2

elementos son todas distintas. Esta propiedad equivale a que las diferencias no cero entre cualquier par de elementos del conjunto son todas distintas. El concepto de conjunto de Sidon puede considerarse en situaciones m´as generales, por ejemplo en grupos conmutativos. En dimensi´on dos, un caso particular de los conjuntos de Sidon es el de “secuencia sonar”, una funci´on f : {1, . . . , n} → {1, . . . , m} tal que su grafo asociado Gf := {(x, f (x)) : 1 ≤ x ≤ n} es un conjunto de Sidon en (Z × Z, +). Su nombre se debe a que tales funciones se usan en aplicaciones a dispositivos tales como el sonar, denominado as´ı por sus siglas en ingl´es “Sound Navigation And Ranging”, que se utiliza como medio de localizaci´ on ac´ ustica. Otras aplicaciones de conjuntos de Sidon en dimensi´on dos se encuentran en sistemas de comunicaciones ´optimos, en criptograf´ıa, en la distribuci´ on de claves en redes de celulares, e incluso en el campo militar [2]. Formalmente, un conjunto de Sidon se define como sigue.

Definición Definici´ on1.1. 1.1. Un conjunto A en un grupo abeliano G notado aditivamente es un conjunto de Sidon, si todas las diferencias a − a con a, a ∈ A, a = a , son distintas. Sean a, m enteros con a < m. Mediante [a, m] se representa el conjunto {a, a + 1, a + 2, . . . , m}. A continuaci´on se define el concepto de secuencia sonar como en [3]. Definici´ on1.2. 1.2. Una funci´ on f : [1, n] → [1, m] tiene la propiedad de diferencias Definición distintas si para todos los enteros h, i, j, con 1 ≤ h ≤ n − 1, 1 ≤ i, j ≤ n − h se tiene que f (i + h) − f (i) = f (j + h) − f (j) =⇒ i = j. (1) Si [1, m] se identifica con el conjunto de representantes de los enteros m´ odulo m y la condici´ on (1) se cambia por (f (i + h) − f (i) ≡ f (j + h) − f (j))

(m´od m) =⇒ i = j,

f tiene la propiedad de diferencias distintas modular.

Definición Definici´ on1.3. 1.3. Una funci´ on f : [1, n] → [1, m] es una secuencia sonar m × n si tiene la propiedad de diferencias distintas. Mientras que f es una secuencia sonar modular m × n si tiene la propiedad de diferencias distintas modular. En este caso se suele decir que f es una secuencia sonar m´ odulo m con n elementos. El siguiente lema, cuya prueba se sigue directamente de la Definici´on 1.1, la Definici´ on 1.3 y del grafo asociado a una secuencia sonar Gf , establece la relaci´on entre conjuntos de Sidon y secuencias sonar. Lema 1.1. Una funci´ on f : [1, n] → [1, m] es una secuencia sonar si y s´ olo si Lema 1.1. el grafo de f , Gf , es un conjunto de Sidon en (Z × Z, +). Similarmente, f es una secuencia sonar modular m × n si y s´ olo si Gf es un conjunto de Sidon en (Z × Zm , +). 34

Secuencias sonar y conjuntos de Sidon3

El problema fundamental en secuencias sonar consiste en investigar el comportamiento asint´ otico de las siguientes funciones: G(m) := m´ ax{n : existe una secuencia sonar m × n}, G(m´ odm) := m´ ax{n : existe una secuencia sonar modular m × n}. Note que G(m) ≥ G (m´ od m). El siguiente lema establece las cotas superiores triviales para dichas funciones.

Lema 1.2. Lema 1.2. Para todo entero positivo m, se tiene que G(m) ≤ 2m y G( m´od m) ≤ m + 1. Demostraci´ n 1.1. Sea f : [1, n] → [1, m] una secuencia sonar. De acuerdo con Demostracióno1.1. el Lema 1.1, todas las parejas (1, f (i + 1) − f (i)), con 1 ≤ i ≤ n − 1, son distintas. As´ı, se tienen n − 1 enteros distintos contenidos en [−m + 1, m − 1], de donde n − 1 ≤ 2m − 1. El caso modular es similar, s´ olo que las n − 1 diferencias se consideran m´ odulo m. El Teorema 4 de [4] establece que G(m) < m + 5m2/3 , para m suficientemente grande. Utilizando el concepto de energ´ıa aditiva y algunas de sus propiedades elementales, en la siguiente secci´on se prueba que G(m) < m + 3,78m2/3 + 4,76m1/3 + 2. En la Secci´ on 3 se usa la construcci´on de conjuntos de Sidon tipo Bose para construir secuencias sonar que implican que G(m´od(q − 1)) = q, para toda q potencia prima. Adem´as se presentan los algoritmos correspondientes a cada construcci´ on, los cuales han sido implementados en MuPAD Pro 4.0. Finalmente, en la Secci´ on 4 se presentan algunos problemas relacionados con el trabajo.

22. Energía aditiva y cotaysuperior para G(m) Energ´ ıa aditiva cota superior para G(m) Sean (G, +) un grupo conmutativo notado aditivamente, y A, B ⊆ G. El conjunto suma y conjunto diferencia asociados con A y B se definen como A + B := {a + b : a ∈ A, b ∈ B}, A − B := {a − b : a ∈ A, b ∈ B}.

La funci´ on representaci´ on de x ∈ G con respecto al conjunto A + B, y A − B se define respectivamente como RA+B (x) := |{(a, b) ∈ A × B : x = a + b}| = |A ∩ (x − B)| , RA−B (x) := |{(a, b) ∈ A × B : x = a − b}| = |A ∩ (B + x)| , Volumen 18 No. 1, agosto 2014

35

4

Revista de Ciencias

R. J. Osorio, D. F. Ruiz, C. A. Trujillo y C. L. Urbano

donde x − B es la reflexi´ on de B mediante x, B + x es la traslaci´on de B mediante x, y |X | denota el cardinal del conjunto finito X . Note que 

x∈A+B

RA−A (0) = |A|,  RA+B (x) = RA−B (x) = |A||B|.

(2)

x∈A−B

Observación Observaci´ on2.1. 2.1. Note que A es un conjunto de Sidon en G si y s´ olo si RA−A (x) ≤ 1 para todo x ∈ G, x= 0. Definición Definici´ on2.1. 2.1. La energ´ıa aditiva entre A y B, que se denota E(A, B), se define como: E(A, B) := |{(a, a , b, b ) ∈ A2 × B 2 : a + b = a + b }|. Note que E(A, B) cuenta el n´ umero de soluciones de la ecuaci´on a + b = a + b , que es equivalente al n´ umero de soluciones de la ecuaci´on a − b = a − b o de la ecuaci´ on a − a = b − b. Esta observaci´on permite establecer las siguientes identidades (ver [5] para una prueba detallada)   2 2 RA+B (x) = RA−B (x) E(A, B) = x∈A+B

x∈A−B



=

x∈(A−A)∩(B−B)

RA−A (x)RB−B (x).

(3)

El siguiente lema, debido a Ruzsa [6], relaciona el cardinal de un conjunto de Sidon en G con el cardinal de un conjunto cualquiera en el mismo grupo. Lema 2.1. Sea A un conjunto de Sidon en G y sea B cualquier subconjunto de G. Entonces   |A| − 1 2 . |A| ≤ |A + B| 1 + |B| Demostraci´ on2.1.2.1. Mediante la desigualdad de Cauchy–Schwartz y las Demostración identidades (2) y (3) se tiene que  2  (|A||B|)2 = RA+B (x) x∈A+B

≤ |A + B| = |A + B|



x∈A+B

2 RA+B (x)



x∈(A−A)∩(B−B)

RA−A (x)RB−B (x).

(4)

Como A es un conjunto de Sidon, entonces RA−A (x) ≤ 1 para todo x = 0. Por lo tanto, la suma de la desigualdad (4) est´ a acotada por  RB−B (x) ≤ |A||B| + |B|2 − |B|, RA−A (0)RB−B (0) + x∈(A−A)∩(B−B) x=0

36

5

Secuencias sonar y conjuntos de Sidon

lo que implica que (|A||B|)2 ≤ |A + B|(|A||B| + |B|2 − |B|)   1 |A| 2 |A| ≤ |A + B| +1− |B| |B|   |A| − 1 2 |A| ≤ |A + B| 1 + |B| probando as´ı la desigualdad deseada. Utilizando el Lema 2.1 se tiene el primer resultado. Teorema 2.1. Si f : [1, n] −→ [1, m] es una secuencia sonar entonces Teorema 2.1. G(m) ≤ m + 3,78m2/3 + 4,76m1/3 + 2. Demostraci´ o2.2. n 2.2. Dado que f es una secuencia sonar, su grafo es un conjunto Demostración de Sidon. Adem´ as se tiene que |Gf | = n y Gf ⊆ [1, n] × [1, m]. Considere el conjunto B = [0, u] × [0, u], donde u = cmα  con α, c > 0. Es claro que |B| = (u + 1)2 . Note que Gf + B ⊆ [1, n + u] × [1, m + u], y por tanto |Gf + B| ≤ (n + u)(m + u). As´ı, de acuerdo con el Lema 2.1 se sigue que   n−1 2 n ≤ (n + u)(m + u) 1 + (u + 1)2   n ≤ (n + u)(m + u) 1 + (u + 1)2   2m α α ≤ (n + cm )(m + cm ) 1 + 2 2α , c m de donde    2 cmα α (m + cm ) 1 + 2 2α−1 n≤ 1+ n c m     c 2 α ≤ 1 + 1−α (m + cm ) 1 + 2 2α−1 m c m   2 α 2 2α−1 = (m + 2cm + c m ) 1 + 2 2α−1 c m 2−2α 2m 4m1−α + 2. + = m + 2cmα + c2 m2α−1 + c2 c √ Luego, con α = 2/3 y c = 3 2 se tiene el resultado deseado. 

3 UnaUna nueva construcción de secuencias sonar 3. nueva construcci´ on de secuencias sonar En esta secci´ on se presenta una nueva construcci´on de secuencias sonar, la cual es un caso particular de la dada en [7]. Esta se basa en la construcci´on de conjuntos de Sidon tipo Bose y algunas propiedades que se desprenden de ella. Volumen 18 No. 1, agosto 2014

37

R. J. Osorio, D. F. Ruiz, C. A. Trujillo y C. L. Urbano6

Revista de Ciencias

3.1 Conjuntos de Sidon Bose 3.1. Conjuntos de tipo Sidon tipo Bose La prueba del Teorema 3.1 y de la Proposici´on 3.1 se presenta en [7]. Teorema 3.1 (Construcci´ on Tipo Bose). Sean q una potencia prima, θ un Teorema 3.1. elemento primitivo en Fq2 y u ∈ F∗q . Entonces, B = B(q, θ, u) := {logθ (uθ + a) : a ∈ Fq },

(5)

es un conjunto de Sidon con q elementos en el grupo aditivo Zq2 −1 . Proposici´ on3.1.3.1. El conjunto B del Teorema 3.1 satisface las siguientes Proposición propiedades. 1. Dados b, b ∈ B, si b = b entonces b ≡ b (m´od q + 1). 2. Para todo b ∈ B, b ≡ 0 (m´ od q + 1). 3. B (m´ od q + 1) := {b (m´ od q + 1) : b ∈ B} = [1, q]. El siguiente algoritmo calcula un conjunto de Sidon tipo Bose en el grupo aditivo Zq2 −1 . Algoritmo 3.1. Bose: Algoritmo 3.1. Bose: Entrada: Un primo p y un entero positivo r. Descripci´ on: Mediante la funci´ on interna de MuPAD Dom::GaloisField(), se crea el campo finito Fq2 y de este se escoge al azar un elemento primitivo mediante randomPrimitive(), para as´ı realizar la asignaci´ on mencionada en el Teorema 3.1. Salida: Una lista de enteros positivos B, que corresponde a un conjunto de Sidon tipo Bose. Bose:=proc(p,r) begin K:=Dom::GaloisField(p,2*r); teta:=K::randomPrimitive(); alfa:=teta^(q+1); q:=p^r; B:=[1]; for j from 1 to q-1 do B:=[op(B),K::ln(teta+alfa^j,teta)]; end_for; return(B); end_proc;

3.2 Construcción de o secuencia sonar sonar 3.2. Construcci´ n de secuencia Haciendo uso del Teorema 3.1 y de la Proposici´on 3.1 se obtiene el siguiente resultado.

Teorema 3.2. Teorema 3.2. Sean q una potencia prima, B el conjunto de Sidon tipo Bose, y para cada i ∈ [1, q] sea bi el u ´nico elemento de B tal que bi ≡ i (m´od q + 1). La funci´ on f : [1, q] −→ [0, q − 2] definida mediante f (i) = bi /(q + 1), es una secuencia sonar m´ odulo q − 1 con q elementos. 38

Secuencias sonar y conjuntos de Sidon7

Demostraci´ n 3.1. Sean h, i, j enteros tales que 1 ≤ h ≤ q − 1 y 1 ≤ i, j ≤ q − h. Demostracióno3.1. Suponga que f (i + h) − f (i) ≡ f (j + h) − f (j) (m´od q − 1), es decir         bi bj+h bj bi+h − ≡ − (m´od q − 1). q+1 q+1 q+1 q+1 Luego existe un entero t tal que 

       bi+h bi bj+h bj − = − + t(q − 1). q+1 q+1 q+1 q+1

As´ı         bi bj+h bj bi+h (q + 1) − (q + 1) = (q + 1) − (q + 1) + t(q 2 − 1). q+1 q+1 q+1 q+1 Sumando h = (i + h) − i = (j + h) − j a ambos lados de la ecuaci´ on se tiene       bi+h bi (q + 1) + (i + h) − (q + 1) + i = q+1 q+1       bj+h bj (q + 1) + (j + h) − (q + 1) + j + t(q 2 − 1). q+1 q+1 Dado que 0 ≤ i + h < q + 1 y 0 ≤ j + h < q + 1, de la u ´ltima igualdad se tiene que bi+h − bi ≡ bj+h − bj (m´ od q 2 − 1). Ya que B es un conjunto de Sidon m´ odulo 2 odulo q − 1 con q q − 1 entonces i = j. Por lo tanto f es una secuencia sonar m´ elementos. El siguiente algoritmo construye una secuencia sonar aplicando el Teorema 3.2. Algoritmo 3.2. SonarN1: Algoritmo 3.2. SonarN1: Entrada: Un primo p y un entero positivo r. Descripci´ on: Mediante el uso del Algoritmo 3.1 y la asignaci´ on descrita en el Teorema 3.2 se construye la secuencia sonar. Salida: Una lista N1 la cual es una secuencia sonar m´ odulo q −1 con q elementos. SonarN1:=proc(p,r) begin B:=Bose(p,r); q:=p^r; N1:=[]; for j from 1 to q do for b in B do if (b mod q+1)=j then N1:=[op(N1), i div q+1]; end_if; end_for; end_for; return(N1); end_proc; Volumen 18 No. 1, agosto 2014

39

R. J. Osorio, D. F. Ruiz, C. A. Trujillo y C. L. Urbano8 8

Revista de Ciencias

el siguiente siguiente ejemplo ejemploseseusa usaelelAlgoritmo Algoritmo3.2 3.2para paraconstruir construir una secuencia En el una secuencia sonar m´ m´ dulo 66 con con 77 elementos. elementos. oodulo Ejemplo 3.1. Sean Sean pp == 77 yyrr==1.1.Mediante MedianteelelAlgoritmo Algoritmo3.13.1 construye Ejemplo 3.1. se se construye un un Ejemplo 3.1. conjunto de Sidon Sidon tipo tipo Bose Bosecon con77elementos elementossobre sobreelelgrupo grupoaditivo aditivo conjunto de Z48Z.48 . B := Bose(7,1); Bose(7,1); BB == [1, [1, 26, 26, 11, 11,5, 5,12, 12,14, 14,31]. 31]. Ahora, continuando continuando con con elel Algoritmo Algoritmo3.2 3.2y ybasado basadoenenel elconjunto conjunto dede Sidon Sidon B se B se construye una secuencia secuenciasonar sonarm´ m´ dulo6 6con con7 7elementos. elementos. construye una oodulo N1 := SonarN1(7,1); SonarN1(7,1); N1 N1 == [0, [0, 3, 3,1, 1,1,1,0,0,1,1,3]. 3].

44. Algunos problemas relacionados Algunos Algunos problemas problemas relacionados relacionados Mediante Mediante b´ b´ uusqueda squedaexhaustiva exhaustivahoy hoyseseconocen conocenvalores valores exactos exactos para para la la funci´ funci´ on on G(m) (algunos (algunos se se muestran muestranen enlalaTabla Tabla1). 1). Tabla Tabla 1: 1: Valores Valoresexactos exactosde deG(m) G(m)y y2m 2m−−G(m), G(m),para para 1≤ 1≤ mm ≤≤ 14.14. m G(m) 2m − G(m) G(m)

11 22 00

22 44 00

33 44 55 6 6 7 7 8 8 9 9 1010 1111 1212 13 13 14 14 66 88 99 1111 1212 1313 1414 1616 1717 1818 19 19 21 21 00 00 11 1 1 2 2 3 3 4 4 4 4 5 5 6 6 7 7 7 7

A partir partir de de ellos ellos es esnatural naturalpreguntarse preguntarsesisi

Problema 1. ¿G(m) Problema Problema 1.1. 1. ¿G(m)≤≤2m 2m−−11para paratodo todoentero enteromm≥≥5 5 Note que que el el resolver resolvereste esteproblema problemaimplica implicauna unamejora mejoraenen la la cota cota superior superior de de G(m) G(m) para valores valores peque˜ peque˜ osde dem. m. nnos De otro otro lado, lado, por por elel Lema Lema 1.2 1.2yyelelTeorema Teorema2.1, 2.1,elelcomportamiento comportamiento cota dede la la cota superior de la la funci´ funci´ G(m),para paratodo todommenenelelintervalo intervalo respectivo, como sigue superior de oonnG(m), respectivo, es es como sigue 2/3 2/3 2/3 1/3 1/3 ≤≤mm++3,78m 3,78m ++4,76m 4,76m ++ 2, 2,m m ∈ [1, ∈ [1, 78]. 78]. G(m) ≤ ≤ 2m 2m ≤ ≤m m++5m 5m2/3 G(m)

2/3 1/3 1/3 2/3 2/3 ++4,76m 4,76m ++2 2≤≤mm ++ 5m 5m , m , m ∈ [79, ∈ [79, 113]. 113]. G(m) G(m) ≤ ≤ 2m 2m ≤ ≤m m++3,78m 3,78m2/3

2/3 1/3 2/3 2/3 ++4,76m 4,76m1/3 ++2 2≤≤2m 2m≤≤mm ++ 5m 5m , m , m ∈ [114, ∈ [114, 125]. 125]. G(m) G(m) ≤ ≤m m+ +3,78m 3,78m2/3

2/3 1/3 2/3 2/3 ++4,76m 4,76m1/3 ++2 2≤≤mm++5m 5m ≤≤ 2m, 2m,m m ≥≥ 126, 126, G(m) G(m) ≤ ≤m m+ +3,78m 3,78m2/3

de donde donde se se sigue sigue elel segundo segundoproblema. problema.

Problema 2. Problema Problema 2.2. 2. Mejorar Mejorar lala cota cotasuperior superiorpara paralalafunci´ funci´ ononG(m). G(m).Relacionado Relacionado concon 2/3 2/3 1/31/3 este problema, problema, en en [4] [4] se se afirma afirmaque queG(m) G(m)≤≤mm++3m 3m + + 2m 2m + + 9, 9, concon lo lo queque se mejorar´ mejorar´ ıa ıa la la cota cota superior superiorde deG(m) G(m)para paravalores valoresgrandes grandesdede m.m. YaYa que que en en [4] [4] no se presenta presenta una una prueba pruebade deeste esteresultado, resultado,y ydedenuestra nuestra parte parte nono haha sido sido posible posible establecerla, establecerla, un unproblema problemaespec´ espec´ ıfico ıficoconsiste consisteenenobtener obtener una una prueba prueba formal formal de de dicha dicha cota.

40

9

Secuencias sonar y conjuntos de Sidon

De la construcci´ on presentada en la Secci´on 3 se infiere que G(q − 1) ≥ q para toda potencia prima q. Adem´as, de los resultados dados en [3], tambi´en se observa que G(m) ≥ m para todo m ≤ 100. De este modo se presentan los siguientes problemas.

Problema 3. 3. Probar o refutar que G(m) ≥ m para todo entero positivo m. Problema Nuestros c´ alculos para otros valores particulares de m nos hace conjeturar que la respuesta es afirmativa. Problema 4. 4. ¿Para cu´ales valores de m se tiene que G (m´od m) = m + 1 y para Problema cu´ales G (m´ od m) = m? Problema 5. Finalmente, un problema que podr´ıa resolver el comportamiento asint´ otico de la funci´ on G(m) para valores grandes de m ser´ıa el estudio del siguiente l´ımite G(m) l´ım m→∞ m Conjeturamos que si el l´ımite anterior existe, este debe ser 1.

Agradecimientos Agradecimientos Los autores agradecen al profesor Javier Cilleruelo por la sugerencia hecha en ALTENCOA5–2012 de usar energ´ıa aditiva con el fin de lograr una mejor cota superior para la funci´ on G(m). Adem´as, se agradece a Colciencias y a la ´ Universidad del Cauca por el apoyo al grupo de investigaci´on “Algebra, Teor´ıa de N´ umeros y Aplicaciones–ALTENUA ERM” bajo los proyectos de investigaci´on con c´odigo 110356935047 y VRI 3744, respectivamente.

Referencias bibliográficas Referencias [1] Drakakis K. (2006). A review of Costas arrays, Journal of Applied Mathematics, 32. [2] Taylor K., Rickard S. and Drakakis K. (2011). Costas arrays: survey, standardization, and matlab toolbox, ACM Transactions on Math. Software 37, (4) 1–31. [3] Moreno O., Games R. and Taylor H. (1993). Sonar sequences from Costas arrays and the best known sonar sequences with up to 100 symbols, IEEE Transactions on Information Theory, 39 (6) 1985–1987. [4] Erdos P., Graham R., Ruzsa I. and Taylor H.(1992). Bounds for arrays of dots with distinct slopes or lengths, Combinatorica, Akad´emiai Kiado-SpringerVerlag 12 (1) 39–44. [5] Tao T. and Vu V. H. (2006). Additive combinatorics, Cambridge Studies in Advanced Mathematics, Cambridge University Press. [6] Ruzsa I. (1993). Solving a linear equation in a set of integers I, Acta Arithmetica 65 (3) 256–282. Volumen 18 No. 1, agosto 2014

41

Revista de Ciencias

10 R. J. Osorio, D. F. Ruiz, C. A. Trujillo y C. L. Urbano

[7] Ruiz D., Caicedo Y. and Trujillo C. (2014). New constructions of sonar sequences, International Journal of Basic and Applied Sciences IJBAS–IJENS 14 (1) 12–16. Direcci´ on de los autores Rigo Juli´ an Osorio Departamento de Matem´ aticas, Universidad del Cauca, Popay´an - Colombia [email protected] Diego Fernando Ruiz Departamento de Matem´ aticas, Universidad del Cauca, Popay´an - Colombia [email protected] Carlos Alberto Trujillo Departamento de Matem´ aticas, Universidad del Cauca, Popay´an - Colombia [email protected] Cristhian Leonardo Urbano Departamento de Matem´ aticas, Universidad del Cauca, Popay´an - Colombia [email protected]

42