Abstract
A set of integers A is called a Sidon set if all the sums of two elements in A are distinct; that is, if for all a, b, c, d ∈ A, we have the implication (a + b = c + d) ⇒{a, b} = {c, d}. The analyst Simon Sidon considered these sets, in the early 1930s, in his research on Fourier analysis. A Golomb ruler is a set of (nonnegative) integers with the property that all nonzero differences are distinct. Such special rules appeared in the study of radio frequency interference carried out byWallace Babcock, at the beginning of the 1950s. The article, of an informative nature, takes a tour through finite contexts in which these mathematical objects intervene. The contexts considered are: finite sets of integers, cyclic groups, two-dimensional integer coordinate lattices (Costas arrays, Sonar sequences) and APN functions. To a large extent, these notes are the partial result of activities carried out during my current sabbatical year at the University of Cauca, and are also an expanded version of the invited conference, that with the same title present during the “55 National Congress of the Mexican Mathematical Society”, held at the University of Guadalajara from 23 to 28 October, 2022 (https://www.smm.org.mx/congreso).
Keywords
References
Atkinson, M., Santoro, Urrutia. (1986). Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters. Transactions on Communications, 34(6), 614-617.
Babcock, W. C. (1953). Intermodulation interference in radio systems frequency of occurrence and control by channel selection. The Bell System Technical Journal, 32(1), 63-73.
Bachoc, C., Serra, O., Zémor, G. (2017). An analogue of vosper’s theorem for extension fields. Mathematical Proceedings of the Cambridge Philosophical Society, 163(3), 423-452.
Balogh, J., Füredi, Z., Roy, S. (2021). An upper bound on the size of sidon sets. arXiv preprint arXiv:2103.15850.
Bloom, G. S., Golomb, S. W. (1977). Applications of numbered undirected graphs. Proceedings of the IEEE, 65(4), 562-570.
Bose, R. (1942). An affine analogue of singer’s theorem. J. Indian Math. Soc, 6(1), 1-15.
Briaud, P., Tillich, J.-P., Verbel, J. (2022). A polynomial time key-recovery attack on the sidon cryptosystem. Selected Areas in Cryptography: 28th International Conference, Virtual Event, September 29-October 1, 2021, Revised Selected Papers, 419-438.
Caicedo, Y., Martos, C. A., Trujillo, C. A. (2015). g− Golomb rulers. Revista Integración, 33(2), 161-172.
Caicedo, Y., Martos, C. A., Trujillo, C. A. (2021). Construcci´on de conjuntos bh en varias dimensiones. Ciencia en Desarrollo, 12(2), 73-81.
Caicedo Bravo, N. Y. (2016). Conjuntos de sid´on en dimensión dos. Tesis de Doctorado, Universidad del Valle.
Campo, L., Mutis,W., Trujillo, C. (2002). Cotas superiores para conjuntos de sidon finitos. Unicauca Ciencia, 7, 95-108.
Carlet, C. (2022). On apn functions whose graphs are maximal sidon sets. Latin American Symposium on Theoretical Informatics, 243-254.
Carlet, C., Mesnager, S. (2022). On those multiplicative subgroups of F2n which are sidon sets and/or sum-free sets. Journal of Algebraic Combinatorics, 55(1), 43-59.
Carlet, C., Picek, S. (2021). On the exponents of APN power functions and sidon sets, sumfree sets, and dickson polynomials. Advances in Mathematics of Communications, 1-19.
Cilleruelo, J. (2010). Sidon sets in Nd. Journal of Combinatorial Theory, Series A, 117(7), 857-871.
Colbourn, C., Dinitz, J. (2007). Handbook of combinatorial designs. CRC press Boca Raton, FL. Costas, J. P. (1975). Medium constraints on sonar design and performance. IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS, 11(5), 973-973.
Costas, J. P. (1984). A study of a class of detection waveforms having nearly ideal range— doppler ambiguity properties. Proceedings of the IEEE, 72(8), 996-1009.
Delgado, L. M. D., Martos, C. A., Trujillo, C. A. (2021). New constructions of extended sonar sequences from sidon sets. IEEE Access, 10, 3343-3350.
Delgado Ordoñez, L. M. (2023). Reglas golomb generalizadas y la teoría de ramsey. Tesis de Doctorado, Departamento de Matemáticas, Universidad del Cauca.
Dimitromanolakis, A. (2002). Analysis of the golomb ruler and the sidon set problems, and determination of large, near-optimal golomb rulers. Master’s Thesis, Department of Electronic and Computer Engineering, Technical University of Crete.
Erdos, P. (1995). Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas do Instituto de Matemática e Estatıstica da Universidade de São Paulo, 2(2), 165-186.
Erdös, P. (1944). On a problem of sidon in additive number theory and on some related problems addendum. Journal of The London Mathematical Society-second Series 19, 208-208.
Erdös, P. (1992). Some of my forgotten problems in number theory. Hardy-Ramanujan Journal, 15, 34-50.
Erdös, P. (1994). Some problems in number theory, combinatorics and combinatorial geometry. Mathematica Pannonica, 5, 261-269.
Erdös, P., Graham, R., Ruzsa, I. Z., Taylor, H. (1992). Bounds for arrays of dots with distinct slopes or lengths. Combinatorica, 12(1), 39-44.
Erdös, P., Turán, P. (1941). On a problem of sidon in additive number theory, and on some related problems. Journal of The London Mathematical Society-second Series, 16, 212-215.
Etzion, T. (2009). Problems on two-dimensional synchronization patterns. Coding and Cryptology: Second InternationalWorkshop, IWCC 2009, Zhangjiajie, China, June 1-5, 2009. Proceedings 2, 52-62.
Gagliardi, R., Robbins, J., Taylor, H. (1987). Acquisition sequences in ppm communications (corresp.) IEEE Transactions on Information Theory, 33(5), 738-744.
Gardner, M. (1972). Graceful graphs of solomon golomb, or how to number a graph parsimoniously. Scientific American, 226(3), 108.
Gilbert, E. N. (1965). Latin squares which contain no repeated digrams. Siam Review, 7(2), 189-198.
Golomb, S., Taylor, H. (1982). Two-dimensional synchronization patterns for minimum ambiguity. IEEE Transactions on Information Theory, 28(4), 600-604.
Golomb, S. W. (1972). How to number a graph. In Graph theory and computing (pp. 23-37). Elsevier. Golomb, S.W. (1984). Algebraic constructions for costas arrays. Journal of CombinatorialmTheory,Series A, 37(1), 13-21.
Halberstam, H., Roth, K. F. (1983). Sequences. Springer Science & Business Media.
Linström, B. (1969). An inequality for B2-sequences. Journal of Combinatorial Theory, 6(2), 211-212.
Martos, C. A., Delgado, L. M., Trujillo, C. A. (2021). Bh sets as a generalization of golomb rulers. IEEE Access, 9, 118042-118050.
Martos, C. A. M., Daza, D. F., Trujillo, C. A. (2021). Near-optimal g-golomb rulers. IEEE Access, 9, 65482-65489.
Martos Ojeda, C. A. (2015). Reglas g− golomb. Tesis de Maestría, Departamento de Matemáticas, Universidad del Cauca.
Martos Ojeda, C. A. (2019). Conjuntos Bh y reglas g− golomb cortas. Tesis de Doctorado, Departamento de Matem´aticas, Universidad del Valle.
Moreno, O., Games, R., Taylor, H. (1991). New constructions and bounds on sonar sequences. Proceedings. 1991 IEEE International Symposium on Information Theory, 283-283.
Moreno, O., Games, R. A., 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.
Niu, M., Xiao, J., Gao, Y. (2022). New constructions of large cyclic subspace codes via sidon spaces. Advances in Mathematics of Communications, 1-15.
O’Bryant, K. (2022). On the size of finite sidon sets. arXiv preprint arXiv:2207.07800.
Raviv, N., Langton, B., Tamo, I. (2021). Multivariate public key cryptosystem from sidon spaces. Public-Key Cryptography–PKC 2021: 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10–13, 2021, Proceedings, Part I, 242-265.
Robinson, J. (1985). Golomb rectangles. IEEE transactions on information theory, 31(6), 781-787.
Robinson, J. P. (1997). Golomb rectangles as folded rulers. IEEE Transactions on Information Theory, 43(1), 290-293.
Ruzsa, I. Z. (1993). Solving a linear equation in a set of integers i. Acta arithmetica, 65(3), 259-282.
Shao, Z., Zhou, J., Liang, M., Lang, F., Xu, X. (2013). Some new golomb rectangles. Journal of Computational and Theoretical Nanoscience, 10(1), 66-68.
Shearer, J. B. (1995). Some new optimum golomb rectangles. The electronic journal of combinatorics, R12.
Shearer, J. B. (2004). Symmetric golomb squares. IEEE transactions on information theory, 50(8), 1846-1847.
Sidon, S. (1932). Ein satz über trigonometrische polynome und seine anwendung in der theorie der fourier-reihen. Mathematische Annalen, 106, 536-539.
Singer, J. (1938). A theorem in finite projective geometry and some applications to number theory. Transactions of the American Mathematical Society, 43(3), 377-385.
Trujillo Solarte, C. A. (1998). Sucesiones de sidon. Tesis de Doctorado, Facultad de Informática, Universidad Politecnica de Madrid.
Zhang, H., Cao, X. (2022). Constructions of sidon spaces and cyclic subspace codes. Frontiers of Mathematics in China, 17(2), 275-288.
Zhang, H., Tang, C. (2023). Constructions of large cyclic constant dimension codes via sidon spaces. Designs, Codes and Cryptography, 91(1), 29-44.
Zhang, T., Ge, G. (2022). New constructions of sidon spaces. Journal of Algebraic Combinatorics, 1–14.
Zullo, F. (2021). Multi-sidon spaces over finite fields. arXiv preprint arXiv:2112.08781.
Zullo, F. (2023). Multi-orbit cyclic subspace codes and linear sets. Finite Fields and Their Applications, 87, 102-153.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright (c) 2023 Revista de la Academia Colombiana de Ciencias Exactas, Físicas y Naturales