Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Equal moments division of a set


Author: Shahar Golan
Journal: Math. Comp. 77 (2008), 1695-1712
MSC (2000): Primary 11B83, 12D10; Secondary 94B05, 11Y99
DOI: https://doi.org/10.1090/S0025-5718-08-02072-3
Published electronically: January 29, 2008
MathSciNet review: 2398788
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ N_q^{*}(m)$ be the minimal positive integer $ N$, for which there exists a splitting of the set $ [0,N-1]$ into $ q$ subsets, $ S_0$, $ S_1$, ..., $ S_{q-1}$, whose first $ m$ moments are equal. Similarly, let $ m_q^{*}(N)$ be the maximal positive integer $ m$, such that there exists a splitting of $ [0,N-1]$ into $ q$ subsets whose first $ m$ moments are equal. For $ q=2$, these functions were investigated by several authors, and the values of $ N_2^{*}(m)$ and $ m_2^{*}(N)$ have been found for $ m\le8$ and $ N\le167$, respectively. In this paper, we deal with the problem for any prime $ q$. We demonstrate our methods by finding $ m_3^*(N)$ for any $ N<90$ and $ N_3^*(m)$ for $ m\le 6$.


References [Enhancements On Off] (What's this?)

  • 1. J.-P. Allouche and J. Shallit, The ubiquitous Prouhet-Thue-Morse sequence, Sequences and their applications, Proceedings of SETA'98 (C. Ding, T. Helleseth & H. Niederreiter, eds.), Spinger-Verlag, 1999, 1-16. MR 1843077 (2002e:11025)
  • 2. D. Berend and S. Golan, Littlewood polynomials with high order zeros, Math. Comp. 75(2006), 1541-1552. MR 2219044 (2007b:11028)
  • 3. D.W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, Math. Comp. 66(1997), 1697-1703. MR 1433263 (98a:11033)
  • 4. D.W. Boyd, On a problem of Byrnes concerning polynomials with restricted coefficients, II, Math. Comp. 71(2002), 1205-1217. MR 1898751 (2003d:11035)
  • 5. J.S. Byrnes, Problems on polynomials with restricted coefficients arising from questions in antenna array theory, Recent Advances in Fourier Analysis and Its Applications (J.S. Byrnes & J.F. Byrnes, eds.), Kluwer Academic Publishers, Dordrecht, 1990, pp. 677-678.
  • 6. J.S. Byrnes and D.J. Newman, Null steering employing polynomials with restricted coefficients, IEEE Trans. Antennas and Propagation 36(1988), 301-303.
  • 7. T.S. Chen and C.N. Yang, An algorithm to enumerate codewords for third-order spectral-null codes, Proceedings, 2004 IEEE International Symposium on Information Theory, p. 88.
  • 8. G. Freiman and S. Litsyn, Asymptotically exact bounds on the size of high-order spectral-null codes, IEEE Trans. Inform. Theory 45(1999), 1798-1807. MR 1720633 (2000k:94060)
  • 9. S. Golan, http://www.cs.bgu.ac.il/~golansha/polynomials.
  • 10. E. M. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Prentice-Hall, New Jersey, 1977. MR 0471431 (57:11164)
  • 11. V. Skachek, T. Etzion and R.M. Roth, Efficient encoding algorithm for third-order spectral-null codes, IEEE Trans. Inform. Theory 44(1998), 846-851. MR 1607751 (98k:94017)
  • 12. R.M. Roth, Spectral-null codes and null spaces of Hadamard submatrices, Designs, Codes and Cryptography 9(1996), 177-191. MR 1409444 (98e:94034)
  • 13. R.M. Roth, P.H. Siegel, and A. Vardy, High-order spectral-null codes: Constructions and bounds, IEEE Trans. Inform. Theory 35(1989), 463-472.
  • 14. L. C. Washington, Introduction to Cyclotomic Fields, Springer, New York, 1982. MR 718674 (85g:11001)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11B83, 12D10, 94B05, 11Y99

Retrieve articles in all journals with MSC (2000): 11B83, 12D10, 94B05, 11Y99


Additional Information

Shahar Golan
Affiliation: Department of Computer Science, Ben-Gurion University of the Negev, POB 653, Beer-Sheva 84105 Israel
Email: golansha@cs.bgu.ac.il

DOI: https://doi.org/10.1090/S0025-5718-08-02072-3
Keywords: Littlewood polynomials, spectral-null code, antenna array
Received by editor(s): March 19, 2007
Received by editor(s) in revised form: May 23, 2007
Published electronically: January 29, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society