Counting solutions without zeros or repetitions of a linear congruence and rarefaction in $b$-multiplicative sequences.

Alexandre Aksenov

doi:10.5802/jtnb.917

Counting solutions without zeros or repetitions of a linear congruence and rarefaction in

b

-multiplicative sequences.

Alexandre Aksenov ¹

¹ Institut Fourier, UMR 5582 100, rue des Maths, BP 74 38402 St Martin d’Hères Cedex FRANCE

Journal de théorie des nombres de Bordeaux, Volume 27 (2015) no. 3, pp. 625-654.

Abstract
Résumé

Consider a strongly $b$ -multiplicative sequence and a prime $p$ . Studying its $p$ -rarefaction consists in characterizing the asymptotic behaviour of the sums of the first terms indexed by the multiples of $p$ . The integer values of the “norm” $3$ -variate polynomial

𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2}) : = \prod_{j = 1}^{p - 1} (Y_{0} + ζ_{p}^{i_{1} j} Y_{1} + ζ_{p}^{i_{2} j} Y_{2}),

where $ζ_{p}$ is a primitive $p$ -th root of unity, and $i_{1}, i_{2} \in {1, 2, \dots,$ $p - 1},$ determine this asymptotic behaviour. It will be shown that a combinatorial method can be applied to $𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2}) .$ The method enables deducing functional relations between the coefficients as well as various properties of the coefficients of $𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2})$ , in particular for $i_{1} = 1$ and $i_{2} = 2, 3$ . This method provides relations between binomial coefficients. It gives new proofs of the two identities $\prod_{j = 1}^{p - 1} (1 - ζ_{p}^{j}) = p$ and $\prod_{j = 1}^{p - 1} (1 + ζ_{p}^{j} - ζ_{p}^{2 j}) = L_{p}$ (the $p$ -th Lucas number). The sign and the residue modulo $p$ of the symmetric polynomials of $1 + ζ_{p} - ζ_{p}^{2}$ can also be obtained. An algorithm for computation of coefficients of $𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2})$ is developed.

Pour une suite fortement $b$ -multiplicative donnée et un nombre premier $p$ fixé, l’étude de la $p$ -raréfaction consiste à caractériser le comportement asymptotique des sommes des premiers termes d’indices multiples de $p$ . Les valeurs entières du polynôme « norme » trivarié

𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2}) : = \prod_{j = 1}^{p - 1} (Y_{0} + ζ_{p}^{i_{1} j} Y_{1} + ζ_{p}^{i_{2} j} Y_{2}),

où $i_{1}, i_{2} \in {1, 2, \dots, p - 1}$ $ζ_{p}$ est une racine $p$ -ième primitive de l’unité, déterminent ce comportement asymptotique. On montre qu’une méthode combinatoire s’applique à $𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2})$ qui permet d’établir de nouvelles relations fonctionnelles entre les coefficients de ce polynôme « norme », diverses propriétés des coefficients de $𝒩_{p, i_{1}, i_{2}} (Y_{0}, Y_{1}, Y_{2})$ , notamment pour $i_{1} = 1, i_{2} = 2, 3$ . Cette méthode fournit des relations entre les coefficients binomiaux, de nouvelles preuves des deux identités $\prod_{j = 1}^{p - 1} (1 + ζ_{p}^{j} - ζ_{p}^{2 j}) = L_{p}$ (le $p$ -ième nombre de Lucas) et $\prod_{j = 1}^{p - 1} (1 - ζ_{p}^{j}) = p$ , le signe et le résidu modulo $p$ des polynômes symétriques des $1 + ζ_{p} - ζ_{p}^{2}$ . Une méthode algorithmique de recherche des coefficients de $𝒩_{p, i_{1}, i_{2}}$ est développée.

DOI: 10.5802/jtnb.917

Classification: 05A10, 05A18, 11B39, 11R18
Keywords: Thue-Morse sequence, b-multiplicative sequences, rarefactions, cyclotomic extensions, Lucas numbers, binomial coefficients, set partitions.

Author's affiliations:

Alexandre Aksenov ¹

¹ Institut Fourier, UMR 5582 100, rue des Maths, BP 74 38402 St Martin d’Hères Cedex FRANCE

@article{JTNB_2015__27_3_625_0,
     author = {Alexandre Aksenov},
     title = {Counting solutions without zeros or repetitions of a linear congruence and rarefaction in $b$-multiplicative sequences.},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {625--654},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {27},
     number = {3},
     year = {2015},
     doi = {10.5802/jtnb.917},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.917/}
}

TY  - JOUR
AU  - Alexandre Aksenov
TI  - Counting solutions without zeros or repetitions of a linear congruence and rarefaction in $b$-multiplicative sequences.
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2015
SP  - 625
EP  - 654
VL  - 27
IS  - 3
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.917/
DO  - 10.5802/jtnb.917
LA  - en
ID  - JTNB_2015__27_3_625_0
ER  -

%0 Journal Article
%A Alexandre Aksenov
%T Counting solutions without zeros or repetitions of a linear congruence and rarefaction in $b$-multiplicative sequences.
%J Journal de théorie des nombres de Bordeaux
%D 2015
%P 625-654
%V 27
%N 3
%I Société Arithmétique de Bordeaux
%U https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.917/
%R 10.5802/jtnb.917
%G en
%F JTNB_2015__27_3_625_0

Alexandre Aksenov. Counting solutions without zeros or repetitions of a linear congruence and rarefaction in $b$-multiplicative sequences.. Journal de théorie des nombres de Bordeaux, Volume 27 (2015) no. 3, pp. 625-654. doi : 10.5802/jtnb.917. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.917/

References
Cited by

[1] A. Aksenov, « Raréfaction dans les suites $b$ -multiplicatives », PhD Thesis, University of Grenoble (France), 2014.

[2] G. Alkauskas, « Dirichlet series associated with strongly $q$ -multiplicative functions », Ramanujan J. 8 (2004), no. 1, p. 13-21. | MR | Zbl

[3] R. C. Baker, G. Harman & J. Pintz, « The difference between consecutive primes. II », Proc. London Math. Soc. (3) 83 (2001), no. 3, p. 532-562. | MR | Zbl

[4] A. T. Benjamin & J. J. Quinn, « The Fibonacci numbers—exposed more discretely », Math. Mag. 76 (2003), no. 3, p. 182-192. | MR | Zbl

[5] F. M. Dekking, « On the distribution of digits in arithmetic sequences », in Seminar on number theory, 1982–1983 (Talence, 1982/1983), Univ. Bordeaux I, Talence, 1983, p. Exp. No. 32, 12. | MR | Zbl

[6] M. Drmota & J. F. Morgenbesser, « Generalized Thue-Morse sequences of squares », Israel J. Math. 190 (2012), p. 157-193. | MR | Zbl

[7] M. Drmota & M. Skałba, « Rarified sums of the Thue-Morse sequence », Trans. Amer. Math. Soc. 352 (2000), no. 2, p. 609-642. | MR | Zbl

[8] A. O. Gelʼfond, « Sur les nombres qui ont des propriétés additives et multiplicatives données », Acta Arith. 13 (1967/1968), p. 259-265. | MR | Zbl

[9] S. Goldstein, K. A. Kelly & E. R. Speer, « The fractal structure of rarefied sums of the Thue-Morse sequence », J. Number Theory 42 (1992), no. 1, p. 1-19. | MR | Zbl

[10] P. J. Grabner, « Completely $q$ -multiplicative functions: the Mellin transform approach », Acta Arith. 65 (1993), no. 1, p. 85-96. | MR | Zbl

[11] R. Hofer, « Coquet-type formulas for the rarefied weighted Thue-Morse sequence », Discrete Math. 311 (2011), no. 16, p. 1724-1734. | MR | Zbl

[12] J. P. S. Kung, G.-C. Rota & C. H. Yan, Combinatorics: the Rota way, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2009, xii+396 pages. | MR | Zbl

[13] F. Luca & R. Thangadurai, « On an arithmetic function considered by Pillai », J. Théor. Nombres Bordeaux 21 (2009), no. 3, p. 693-699. | Numdam | MR | Zbl

[14] M. Petkovšek, H. S. Wilf & D. Zeilberger, $A = B$ , A K Peters, Ltd., Wellesley, MA, 1996, With a foreword by Donald E. Knuth, With a separately available computer disk, xii+212 pages. | MR | Zbl

[15] G.-C. Rota, « On the foundations of combinatorial theory. I. Theory of Möbius functions », Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), p. 340-368 (1964). | MR | Zbl

[16] J. A. Sloane, « On-Line Encyclopedia of Integer Sequences », http://oeis.org.

[17] R. P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997, With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original, xii+325 pages. | MR | Zbl

[18] B. M. Trager, « Algebraic factoring and rational function integration. », Symbolic and algebraic computation, Proc. 1976 ACM Symp., Yorktown Heights/N.Y., 219-226 (1976)., 1976. | Zbl

Cited by Sources: