Linear recurrence sequences without zeros

Artūras Dubickas; Aivaras Novikas

Czechoslovak Mathematical Journal (2014)

  • Volume: 64, Issue: 3, page 857-865
  • ISSN: 0011-4642

Abstract

top
Let a d - 1 , ⋯ , a 0 ∈ ℤ , where d ∈ ℕ and a 0 ≠ 0 , and let X = ( x n ) n = 1 ∞ be a sequence of integers given by the linear recurrence x n + d = a d - 1 x n + d - 1 + ⋯ + a 0 x n for n = 1 , 2 , 3 , ⋯ . We show that there are a prime number p and d integers x 1 , ⋯ , x d such that no element of the sequence X = ( x n ) n = 1 ∞ defined by the above linear recurrence is divisible by p . Furthermore, for any nonnegative integer s there is a prime number p ≥ 3 and d integers x 1 , ⋯ , x d such that every element of the sequence X = ( x n ) n = 1 ∞ defined as above modulo p belongs to the set { s + 1 , s + 2 , ⋯ , p - s - 1 } .

How to cite

top

Dubickas, Artūras, and Novikas, Aivaras. "Linear recurrence sequences without zeros." Czechoslovak Mathematical Journal 64.3 (2014): 857-865. <http://eudml.org/doc/262135>.

@article{Dubickas2014,
abstract = {Let $a_\{d-1\},\dots ,a_0 \in \mathbb \{Z\}$, where $d \in \mathbb \{N\}$ and $a_0 \ne 0$, and let $X=(x_n)_\{n=1\}^\{\infty \}$ be a sequence of integers given by the linear recurrence $x_\{n+d\}=a_\{d-1\}x_\{n+d-1\}+\dots +a_0x_\{n\}$ for $n=1,2,3,\dots $. We show that there are a prime number $p$ and $d$ integers $x_1,\dots ,x_d$ such that no element of the sequence $X=(x_n)_\{n=1\}^\{\infty \}$ defined by the above linear recurrence is divisible by $p$. Furthermore, for any nonnegative integer $s$ there is a prime number $p \ge 3$ and $d$ integers $x_1,\dots ,x_d$ such that every element of the sequence $X=(x_n)_\{n=1\}^\{\infty \}$ defined as above modulo $p$ belongs to the set $\lbrace s+1,s+2,\dots ,p-s-1\rbrace $.},
author = {Dubickas, Artūras, Novikas, Aivaras},
journal = {Czechoslovak Mathematical Journal},
keywords = {linear recurrence sequence; period modulo $p$; polynomial splitting in $\mathbb \{F\}_p[z]$; linear recurrence sequence; period modulo ; characteristic polynomial of a sequence; polynomial splitting in $\mathbb \{F\}_p[z]$},
language = {eng},
number = {3},
pages = {857-865},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Linear recurrence sequences without zeros},
url = {http://eudml.org/doc/262135},
volume = {64},
year = {2014},
}

TY - JOUR
AU - Dubickas, Artūras
AU - Novikas, Aivaras
TI - Linear recurrence sequences without zeros
JO - Czechoslovak Mathematical Journal
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 64
IS - 3
SP - 857
EP - 865
AB - Let $a_{d-1},\dots ,a_0 \in \mathbb {Z}$, where $d \in \mathbb {N}$ and $a_0 \ne 0$, and let $X=(x_n)_{n=1}^{\infty }$ be a sequence of integers given by the linear recurrence $x_{n+d}=a_{d-1}x_{n+d-1}+\dots +a_0x_{n}$ for $n=1,2,3,\dots $. We show that there are a prime number $p$ and $d$ integers $x_1,\dots ,x_d$ such that no element of the sequence $X=(x_n)_{n=1}^{\infty }$ defined by the above linear recurrence is divisible by $p$. Furthermore, for any nonnegative integer $s$ there is a prime number $p \ge 3$ and $d$ integers $x_1,\dots ,x_d$ such that every element of the sequence $X=(x_n)_{n=1}^{\infty }$ defined as above modulo $p$ belongs to the set $\lbrace s+1,s+2,\dots ,p-s-1\rbrace $.
LA - eng
KW - linear recurrence sequence; period modulo $p$; polynomial splitting in $\mathbb {F}_p[z]$; linear recurrence sequence; period modulo ; characteristic polynomial of a sequence; polynomial splitting in $\mathbb {F}_p[z]$
UR - http://eudml.org/doc/262135
ER -

References

top
  1. Adleman, L. M., Odlyzko, A. M., 10.1090/S0025-5718-1983-0717715-6, Math. Comput. 41 (1983), 699-709. (1983) Zbl0527.12002MR0717715DOI10.1090/S0025-5718-1983-0717715-6
  2. Carroll, D., Jacobson, E., Somer, L., Distribution of two-term recurrence sequences mod p e , Fibonacci Q. 32 (1994), 260-265. (1994) MR1285757
  3. Dubickas, A., Distribution of some quadratic linear recurrence sequences modulo 1, Carpathian J. Math. 30 (2014), 79-86. (2014) MR3244094
  4. Dubickas, A., 10.1112/S0024609305017728, Bull. Lond. Math. Soc. 38 (2006), 70-80. (2006) Zbl1164.11025MR2201605DOI10.1112/S0024609305017728
  5. Dubickas, A., 10.1016/j.jnt.2005.07.004, J. Number Theory 117 (2006), 222-239. (2006) Zbl1097.11035MR2204744DOI10.1016/j.jnt.2005.07.004
  6. Everest, G., Poorten, A. van der, Shparlinski, I., Ward, T., 10.1090/surv/104/06, Mathematical Surveys and Monographs 104 American Mathematical Society, Providence (2003). (2003) MR1990179DOI10.1090/surv/104/06
  7. Kaneko, H., Limit points of fractional parts of geometric sequences, Unif. Distrib. Theory 4 (2009), 1-37. (2009) Zbl1249.11066MR2557644
  8. Kaneko, H., 10.1007/s00025-008-0287-3, Result. Math. 52 (2008), 91-109. (2008) Zbl1177.11060MR2430415DOI10.1007/s00025-008-0287-3
  9. Lagarias, J. C., Odlyzko, A. M., Effective versions of the Chebotarev density theorem, Algebraic Number Fields: -Functions and Galois Properties Proc. Symp., Durham, 1975 A. Fröhlich Academic Press, London (1977), 409-464. (1977) Zbl0362.12011MR0447191
  10. Laksov, D., 10.7146/math.scand.a-10759, Math. Scand. 16 (1965), 181-196. (1965) Zbl0151.01502MR0194349DOI10.7146/math.scand.a-10759
  11. Lidl, R., Niederreiter, H., Introduction to Finite Fields and Their Applications, Cambridge University Press Cambridge (1994). (1994) Zbl0820.11072MR1294139
  12. Neukirch, J., 10.1007/978-3-662-03983-0, Grundlehren der Mathematischen Wissenschaften 322 Springer, Berlin (1999). (1999) Zbl0956.11021MR1697859DOI10.1007/978-3-662-03983-0
  13. Niederreiter, H., Schinzel, A., Somer, L., Maximal frequencies of elements in second-order linear recurring sequences over a finite field, Elem. Math. 46 (1991), 139-143. (1991) Zbl0747.11062MR1119645
  14. Ribenboim, P., Walsh, G., 10.1006/jnth.1998.2315, J. Number Theory 74 (1999), 134-147. (1999) Zbl0923.11033MR1670556DOI10.1006/jnth.1998.2315
  15. Schinzel, A., Polynomials with special regard to reducibility, Encyclopedia of Mathematics and Its Applications 77 Cambridge University Press, Cambridge (2000). (2000) Zbl0956.12001MR1770638
  16. Schinzel, A., Special Lucas sequences, including the Fibonacci sequence, modulo a prime, A Tribute to Paul Erdős A. Baker, et al. Cambridge University Press Cambridge (1990), 349-357. (1990) Zbl0716.11009MR1117027
  17. Somer, L., Distribution of residues of certain second-order linear recurrences modulo p , Applications of Fibonacci Numbers, Vol. 3 G. E. Bergum, et al. Proc. 3rd Int. Conf., Pisa, 1988 Kluwer Academic Publishers Group, Dordrecht (1990), 311-324. (1990) Zbl0722.11008MR1125803
  18. Somer, L., Primes having an incomplete system of residues for a class of second-order recurrences, Applications of Fibonacci Numbers, Proc. 2nd Int. Conf. A. N. Philippou, et al. Kluwer Academic Publishers Dordrecht (1988), 113-141. (1988) Zbl0653.10005MR0951911
  19. P. Stevenhagen, H. W. Lenstra, Jr., 10.1007/BF03027290, Math. Intell. 18 (1996), 26-37. (1996) Zbl0885.11005MR1395088DOI10.1007/BF03027290
  20. Voloch, J. F., 10.5802/jtnb.266, J. Théor. Nombres Bordx. 12 (2000), 81-85. (2000) Zbl1007.11069DOI10.5802/jtnb.266
  21. Zaïmi, T., 10.1016/j.jnt.2005.11.012, J. Number Theory 120 (2006), 179-191. (2006) Zbl1147.11037MR2256803DOI10.1016/j.jnt.2005.11.012
  22. Zheng, Q.-X., Qi, W.-F., Tian, T., 10.1007/s10623-012-9698-y, Des. Codes Cryptography 70 (2014), 359-368. (2014) MR3160735DOI10.1007/s10623-012-9698-y
  23. Zhuravleva, V., 10.5802/jtnb.846, J. Théor. Nombres Bordx. 25 (2013), 499-520. (2013) Zbl1283.11102MR3228318DOI10.5802/jtnb.846
  24. Zhuravleva, V., 10.1134/S0001434613110163, Math. Notes 94 (2013), 820-823 translation from Mat. Zametki 94 784-787 (2013). (2013) Zbl1284.11106MR3227021DOI10.1134/S0001434613110163

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.