Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

Equal moments division of a set

Author(s): Shahar Golan.
Journal: Math. Comp. 77 (2008), 1695-1712.
MSC (2000): Primary 11B83, 12D10; Secondary 94B05, 11Y99
Posted: January 29, 2008
Retrieve article in: PDF DVI PostScript

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:

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: 10.1090/S0025-5718-08-02072-3
PII: S 0025-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
Posted: January 29, 2008
Copyright of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google