{"entities":{"Q933420":{"pageid":935268,"ns":120,"title":"Item:Q933420","lastrevid":65509434,"modified":"2026-04-12T03:06:09Z","type":"item","id":"Q933420","labels":{"en":{"language":"en","value":"The asymptotic normalized linear complexity of multisequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5303165"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$7BD53D08-8BCE-40F8-A17C-4B4755D9DF1B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c71b4a2c54e53b07140d535efd4cc70ff3d55de","datavalue":{"value":{"text":"The asymptotic normalized linear complexity of multisequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q933420$D4A5F437-68C1-4447-9DB1-84312F3ABEEE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"537bbfc51534cf869c7f4ed4d1087dfc0347ad50","datavalue":{"value":"1165.11063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$12DF061D-6FF5-4394-99B6-2C00C21F6DD9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f72a35da5b58000aa3823aaab5581a547e1681dd","datavalue":{"value":{"entity-type":"item","numeric-id":272765,"id":"Q272765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$7980B8A7-BFCC-441A-B813-852041029EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3717a94342cd041afe501f03cf92fca2725c5056","datavalue":{"value":{"entity-type":"item","numeric-id":933419,"id":"Q933419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$95817D37-2F7D-4FE1-88C8-63B4AF990E30","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$1453318B-8609-4DBF-B838-9BB424024A3A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ef23f451c63fbed589b4692fdb97271c9dafb789","datavalue":{"value":{"time":"+2008-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q933420$98A07749-2B1E-4FD5-92EE-42154B98E92D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"13f8b18ca6aaacfe76f266291f186bbdc45cf0f2","datavalue":{"value":"https://arxiv.org/abs/0705.4138","type":"string"},"datatype":"url"},"type":"statement","id":"Q933420$8D642B6F-AB93-44B0-81CF-D9883B2CE24C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6736662eda372e710c3613ba4bb5b42f29024af3","datavalue":{"value":"Let \\(q\\) be a prime power and \\({\\mathbb F}_q\\) the finite field of order \\(q\\). Let \\(M \\in {\\mathbb N}\\). For all multisequences \\(a = (a_{m,t}) \\in {\\mathbb F}_q^{M\\times{\\mathbb N}}\\) and all \\(m \\in [M] := \\{1, \\dots , M\\}\\) the authors denote by \\(G_m\\) the formal power series  \\[ G_m := \\sum_{t=1}^{\\infty}a_{m,t}x^{-t} \\in {\\mathbb F}_q[x^{-1}]. \\]  The linear complexity \\(L_a\\) of a multisequence \\(a \\in {\\mathbb F}_q^{M\\times{\\mathbb N}}\\) is defined through  \\[ L_a(n) := \\min\\{ \\deg{v} \\mid v \\in {\\mathbb F}_q[x] ,\\quad \\forall m \\in [M] \\quad \\exists u_m \\in {\\mathbb F}_q[x]:\\;G_m = \\frac{u_m(x)}{v(x)} + o(x^{-n})\\}. \\]  for all \\(n \\in {\\mathbb N}\\). The asymptotic lower bound for the normalized linear complexity of a multisequence \\(a \\in {\\mathbb F}_q^{M\\times{\\mathbb N}}\\) is then defined by  \\[ I := \\liminf_{n \\to \\infty} \\frac{L_a(n)}{n}. \\]  The asymptotic upper bound for the normalized linear complexity of a multisequence \\(a \\in {\\mathbb F}_q^{M\\times{\\mathbb N}}\\) is defined similarly as  \\[ S := \\limsup_{n \\to \\infty} \\frac{L_a(n)}{n}. \\]  It is shown that if for all \\(m \\in [M]\\) the sequence \\((a_{m,t})_{t \\in {\\mathbb N}}\\) has nonzero discrepancy infinitely often (here the definition of discrepancy is taken from [\\textit{Z. Dai, X. Feng} and \\textit{J. Yang}, SETA 2004, Lect. Notes Comput. Sci. 3486, 339--354 (2005; Zbl 1145.94413)], where it is defined for \\(q=2\\)), then it holds that  \\[ \\frac{M}{M+1} \\leq S \\leq 1 \\quad\\text{and}\\quad M(1-S) \\leq I \\leq 1-\\frac{S}{M}. \\]  This answers an Open Problem posed in [\\textit{Z. Dai, K. Imamura} and \\textit{J. Yang}, SETA 2004, Lect. Notes Comput. Sci. 3486, 129--142 (2005; Zbl 1145.94414)].  Furthermore it is shown that for all \\((I,S)\\) there are \\(\\left| {\\mathbb F}_q^{M\\times{\\mathbb N}} \\right|\\) multisequences having \\(I,S\\) as respective bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q933420$45744B82-70A7-443F-A5E5-A2D10E21F28B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d503c2183e475a61583573b55fab6564130a2db5","datavalue":{"value":{"entity-type":"item","numeric-id":211679,"id":"Q211679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$DBE673E9-9DFA-4D52-8211-8FF92D2F964A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"086c0286ca441f85b3f6a04f4cff158d1709cb93","datavalue":{"value":"11K38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$E1FC5B9B-7B2F-439E-8086-63E3A657E857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c095d1505d4b373846db7ba89cc1ad77e725945f","datavalue":{"value":"94A55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$4DDA1254-D2D2-4C7F-9567-A5935803ABA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$607C3517-828B-4832-9A1D-F3488DE8ACB9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba1c7f5baa976faf3098e8f48398b88cad789b8d","datavalue":{"value":"5303165","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$4FEF5305-C95C-4981-BEE5-C22CC6D51002","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a55fb7e70a0a30faba9d447ff633fcbf884168f","datavalue":{"value":"linear complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q933420$496F8C46-BB80-479F-946C-86EE47F68EE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"005a544a90661e113ae43fe5cedc4db9ed7011c6","datavalue":{"value":"multisequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q933420$A2B20E19-2CAA-4729-B0A1-D7EFFB6CC21A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf56d1c54f183e1446df276cd6e2a5e6504dd20b","datavalue":{"value":"battery discharge model","type":"string"},"datatype":"string"},"type":"statement","id":"Q933420$B797C10E-F498-4DF7-A054-86920AA1A19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"111e0b12ef4b66b4c5bd4b731db2cb9dc73af304","datavalue":{"value":"isometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q933420$107400DB-49F5-4800-B05F-FC1855FEF146","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$04EBCEA1-5ED9-43E1-B2B5-058387E2D098","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"59130cffc4c96bb189df642bfd7e35b0e20b9d95","datavalue":{"value":"W2091745612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$5845ED38-6BA1-491B-AF12-A53B77540A28","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb7e91d24d7103a646c42896256ac01c618fed31","datavalue":{"value":{"entity-type":"item","numeric-id":3541904,"id":"Q3541904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$DC6D73E5-7073-4BCD-9DC9-F1C64ECF6FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68e96a648fc1bf503c97ac91d97676f909578550","datavalue":{"value":{"entity-type":"item","numeric-id":5450841,"id":"Q5450841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$C413099A-0215-4951-9C29-B9CB8589870E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"188a8844d858fab8746774f26a8c13db1ee33138","datavalue":{"value":{"entity-type":"item","numeric-id":5450820,"id":"Q5450820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$381E0748-EE4F-498D-8319-155C222FAD6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5b494137280218f1b44135e1a94fc319d0488d7","datavalue":{"value":{"entity-type":"item","numeric-id":3546748,"id":"Q3546748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$F3F5541F-3D08-4034-8F95-3AEFB917EFB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52fcee9f404eb51f4339c152bccda9be9ed201c4","datavalue":{"value":{"entity-type":"item","numeric-id":5450973,"id":"Q5450973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$CEEF74F4-4F89-4243-804E-88030B8FF1DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"baac2af8883552f0c17674500d5233807c0d586a","datavalue":{"value":{"entity-type":"item","numeric-id":877184,"id":"Q877184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$76E9F4A0-EE57-420F-B42A-E2B78AF27F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f8aa73d55cf13370a12d32afc5b33e629b1878","datavalue":{"value":{"entity-type":"item","numeric-id":5450821,"id":"Q5450821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$881D5740-0045-46EE-A854-F38C56C0AE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72889143a7d3426b3f7ba930e65e3ec61e677273","datavalue":{"value":{"entity-type":"item","numeric-id":998652,"id":"Q998652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q933420$0210383E-368A-4EEF-80D9-96B23285F4C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7bdbcda35ce5c0039039e6f5722c67d8e1618720","datavalue":{"value":"10.1016/J.JCO.2007.11.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q933420$32D5CE0B-B8A3-444E-BA2B-58B17B697574","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b52eeaff23391c8042a14ff8a7479a30b033667","datavalue":{"value":{"entity-type":"item","numeric-id":5450820,"id":"Q5450820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"290126d17fb11a4938b667afea40180ad6142025","datavalue":{"value":{"amount":"+0.7578801","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$F20CD70E-BFFB-4087-9DCB-6D274DF6C8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51606d14f9fb1f6044de8c6d9f8243ba2aba17aa","datavalue":{"value":{"entity-type":"item","numeric-id":1791680,"id":"Q1791680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c8cf5efe34dace6c41cfa9146335049b9da409f","datavalue":{"value":{"amount":"+0.74389654","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$B9FD7C9D-1032-4171-B40A-9408F0957C3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dc336bafa6d2a3b73ad82cd96c6ad4224292607","datavalue":{"value":{"entity-type":"item","numeric-id":5450818,"id":"Q5450818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0771d4c09d8a74cf71999ae22b34c30c3ac48eb2","datavalue":{"value":{"amount":"+0.74281573","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$66F9B0EF-9E3E-4CEC-854B-12FE25953843","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de2a63f2420116d062c99c1ff3a19086ebca395d","datavalue":{"value":{"entity-type":"item","numeric-id":2860223,"id":"Q2860223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e06299617300c5948ad0585dad36e8de958fc383","datavalue":{"value":{"amount":"+0.73672175","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$76F3E1AD-CEB3-43FD-BA46-9B8C36DEF06D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f7ce0d3be1bc603928a3370ae1dda3b9ffe45a5","datavalue":{"value":{"entity-type":"item","numeric-id":877184,"id":"Q877184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c1bdc6d46a92a3ee297771bff89f7f2c02301c6","datavalue":{"value":{"amount":"+0.7324046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$D70622A9-DAA2-40F0-9F96-D74AE5275058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c98fafda0673ddf452977f2c53067c81301ec46b","datavalue":{"value":{"entity-type":"item","numeric-id":609363,"id":"Q609363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce819779489611770c49bf7162b68489db8e44c5","datavalue":{"value":{"amount":"+0.7266572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$A546D01C-C30E-4403-BDBB-66643EEA8B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43dd1b4bf750c218f41142ca35324f4f57494a2f","datavalue":{"value":{"entity-type":"item","numeric-id":2517819,"id":"Q2517819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88d93f63b957c961a7eb8086fe3ce86079d4a18d","datavalue":{"value":{"amount":"+0.7260281","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$051409EB-8790-422B-87CB-5EAE6EA76958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbcaf277daed929eb5a262edc658b31f517f488d","datavalue":{"value":{"entity-type":"item","numeric-id":3062258,"id":"Q3062258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbd4b96eaa1709b52de1baf533e2eaeefdb8fb00","datavalue":{"value":{"amount":"+0.7258143","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q933420$D313EFA2-DD7E-437C-B63E-D879BC44C1E1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The asymptotic normalized linear complexity of multisequences","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_asymptotic_normalized_linear_complexity_of_multisequences"}}}}}