0,1 distribution in the highest level sequences of primitive sequences over<Emphasis Type="Italic">Z</Emphasis><Subscript>2e</Subscript>

In this paper, we discuss the 0,1 distribution in the highest level sequence a_e-1 of primitive sequence over Z_2e generated by a primitive polynomial of degreen. First we get an estimate of the 0,1 distribution by using the estimates of exponential sums over Galois rings, which is tight fore relatively small ton. We also get an estimate which is suitable fore relatively large ton. Combining the two bounds, we obtain an estimate depending only onn, which shows that the largern is, the closer to 1/2 the proportion of 1 will be.     

GR(4,r)上本原序列的元素分布

本文利用GR（4，r)上本原序列的迹表示及二次型的有关结论，给出了本原序列的第一权位序列的元素分布，同时求得本原序列的元素分布。     

Zpe上本原序列的元素分布

文研究了Zpe上本原序列的元素分布.利用Ga,lois环上的指数和估计和本原序列的迹表示,得到了Zpe中各元素在本原序列的一个周期中出现频率的一个估计.当n＞4e时(n为本原序列生成多项式的次数).我们的估计优于Kuzmin的结果[1].     

Zpe上本原序列的元素分布

文研究了Z_p^e上本原序列的元素分布。利用Galois环上的指数和估计和本原序列的迹表示,得到了Z_p^e中各元素在本原序列的一个周期中出现频率的一个估计。当n>4e时(n为本原序列生成多项式的次数),我们的估计优于Kuzmin的结果。     

Galois环上本原序列压缩映射的单性

设Ω是 Ｇａｌｏｉｓ环 ＧＲ（２~ｄ,ｒ）的 Ｔｅｉｃｈｍｕｌｌｅｒ代表集,则 ＧＲ（２~ｄ,ｒ）上每条序列ａ有唯一的权位分解,　其中ａ-ｉ是Ω上序列,同时也可自然视为有限域Ｆ-（２~ｒ）,上序列．设ｆ（ｘ）是环 ＧＲ（２~ｄ,ｒ）上强本原多项式,Ｇ（ｆ（ｘ））表示 ＧＲ（２~ｄ,ｒ）上以ｆ（ｘ）为特征多项式的序列的全体,是Ｆ-（２~ｒ）上一类ｄ－１元多项式, 　本文证明了压缩映射是单射,即对 ａ＝ ｂ当且仅当对所有 ａ,ｂ ∈ Ｇ（ｆ（ｘ））．     

环导出序列的单一性及还原算法

在文献 ［１］中,从 Ｚ２ｎ上的某些线性递归序列到它的最高位坐标序列的映射的单一性已被证明;本文利用序列的迹表示将此结论推广到任意特征的 Ｇａｌｏｉｓ环上,并且给出一个算法,在已知特征多项式和最高位坐标序列的条件下,还原出本来的环上序列．     

INJECTIVE MAPS ON PRIMITIVE SEQUENCES OVER Z/（p^e）

Let Z/(pe) be the integer residue ring modulo pe with p an odd prime and integer e ≥ 3. For a sequence (a) over Z/(pe), there is a unique p-adic decomposition (a) = (a)0 (a)1·p … (a)e-1 ·pe-1, where each (a)i can be regarded as a sequence over Z/(p), 0 ≤ i ≤ e - 1. Let f(x) be a primitive polynomial over Z/(pe) and G' (f(x), pe) the set of all primitive sequences generated by f(x) over Z/(pe). For μ(x) ∈ Z/(p)[x] with deg(μ(x)) ≥ 2 and gcd(1 deg(μ(x)),p- 1) = 1,set ψe-1 (x0, x1,…, xe-1) = xe-1·[ μ(xe-2) ηe-3 (x0, x1,…, xe-3)] ηe-2 (x0, x1,…, xe-2),which is a function of e variables over Z/(p). Then the compressing map ψe-1: G'(f(x),pe) → (Z/(p))∞,(a) (→)ψe-1((a)0, (a)1,… ,(a)e-1) is injective. That is, for (a), (b) ∈ G' (f(x), pe), (a) = (b) if and only if ψe - 1 ((a)0, (a)1,… , (a)e - 1) =ψe - 1 ((b)0,(b)1,… ,(b)e-1). As for the case of e = 2, similar result is also given. Furthermore, if functions ψe-1 and ψe-1 over Z/(p) are both of the above form and satisfy ψe-1((a)0,(a)1,… ,(a)e-1) = ψe-1((b)0,(b)1,… ,(b)e-1) for (a),(b) ∈ G'(f(x),pe), the relations between (a) and (b), ψe-1 and ψe-1 are discussed.     

环Z/(p~e)上本原序列压缩映射的新结果

令Z/(pe)表示整数剩余类环,其中p为素数且e 2为正整数.令f(x)表示Z/(pe)上的n次本原多项式,G′(f(x),pe)表示Z/(pe)上所有由f(x)生成的本原序列构成的集合.设序列a∈G′(f(x),pe),它有唯一的p进制展开a=a0+a1p+···+ae-1pe-1.令φ(x0,x1,...,xe-1)=g(xe-1)+μ(x0,x1,...,xe-2)表示由Fe p到Fp的一个e变元多项式.那么,φ可以诱导出一个从G′(f(x),pe)到F∞p的压缩映射.在p为奇素数且f(x)为强本原多项式的条件下,人们已经证明该压缩映射是保熵的.而本文证明该压缩映射在f(x)为本原多项式的条件下仍然是保熵的.当deg(g(x))2时,我们还要求deg(g(x))为奇数,或者g(x)=xk+∑k-2i=0cixi.     

Compressing Mappings on Primitive Sequences over Z/(2) and Its Galois Extension

Let f(x) be a strongly primitive polynomial of degree n over Z/(2^e), η(x₀,x₁,…,x_e−2) a Boolean function of e−1 variables and (x₀,x₁,…,x_e−1)=x_e−1+η(x₀,x₁,…,x_e−2)G (f(x),Z/(2^e)) denotes the set of all sequences over Z/(2^e) generated by f(x), F₂^∞ the set of all sequences over the binary field F₂, then the compressing mapping

Full-size image

is injective, that is, for , G(f(x),Z/(2^e)), = if and only if Φ( )=Φ( ), i.e., ( ₀,…, _e−1)=( ₀,…, _e−1) mod 2. In the second part of the paper, we generalize the above result over the Galois rings.     

Primitive polynomial with three coefficients prescribed

The authors proved in Fan and Han (Finite Field Appl., in press) that, for any given (a₁,a₂,a₃)F_q³, there exists a primitive polynomial f(x)=xⁿ−σ₁xⁿ⁻¹++(−1)ⁿσ_n over F_q of degree n with the first three coefficients σ₁,σ₂,σ₃ prescribed as a₁,a₂,a₃ when n8. But the methods in Fan and Han (in press) are not effective for the case of n=7. Mills (Existence of primitive polynomials with three coefficients prescribed, J. Algebra Number Theory Appl., in press) resolves the n=7 case for finite fields of characteristic at least 5. In this paper, we deal with the remaining cases and prove that there exists a primitive polynomial of degree 7 over F_q with the first three coefficient prescribed where the characteristic of F_q is 2 or 3.     

Parametric decomposition of powers of ideals versus regularity of sequences

Let be an ideal in a Noetherian local ring . Then the sequence is -regular if every is a non-zerodivisor in and if for all integers , where runs over the elements of the set .

     

实现同一度序列的图的最大团数

图G中最大完全子图的阶数称为G的团效．ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数．Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题．他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3)．在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法．     

Galois环上的本原多项式的一个判别准则

本文给出Ｇａｌｏｉｓ环Ｒ上的基本不可约多项式ｆ（ｘ）的根的具体表达式和其阶的联系；由此，对本原多项式和次本原多项式分别推导出代数判别式，其主要部分分别由ｆ（ｘ）ｍｏｄｐ和ｆ（ｘ）ｍｏｄｐ２的系数所确定．     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r, n) such that every n-term graphic sequence π = (d1, d2,..., dn) with term sum σ(π) = d1 + d2 +…+ dn ≥σ(Kr,r, n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. πr has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined.     

Distribution of 0 and 1 in the highest level of primitive sequences over ℤ/(2e)

The distribution of 0 and 1 is studied in the highest levela _e-1 of primitive sequences overZ /(2^e). and the upper and lower bounds on the ratio of the number of 0 to the number of 1 in one period ofa _e-1, are obtained. It is revealed that the largere is, the closer to 1 the ratio will be. Project supported by the State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences.     

Behaving sequences

Let S be a sequence over an additively written abelian group. We denote by h(S) the maximum of the multiplicities of S, and by ∑(S) the set of all subsums of S. In this paper, we prove that if S has no zero-sum subsequence of length in [1,h(S)], then either |∑(S)|?2|S|−1, or S has a very special structure which implies in particular that ∑(S) is an interval. As easy consequences of this result, we deduce several well-known results on zero-sum sequences.     

Extended skolem sequences

A k-extended Skolem sequence of order n is an integer sequence (s₁, s₂,…, s_2n+1) in which s_k = 0 and for each j ? {1,…,n}, there exists a unique i ? {1,…, 2n} such that s_i = s_i+j = j. We show that such a sequence exists if and only if either 1) k is odd and n ≡ 0 or 1 (mod 4) or (2) k is even and n ≡ 2 or 3 (mod 4). The same conditions are also shown to be necessary and sufficient for the existence of excess Skolem sequences. Finally, we use extended Skolem sequences to construct maximal cyclic partial triple systems. © 1995 John Wiley & Sons, Inc.     

Derived sequences and reverse mathematics

One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR₀. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR₀. In actuality, the full strength of ATR₀ is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR₀, using only RCA₀ and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman ([3], [4]), which can be roughly characterized by the strength of their set comprehension axioms. RCA₀ includes comprehension for Δ definable sets, ACA₀ includes comprehension for arithmetical sets, and ATR₀ appends to ACA₀ a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99.     

MDS codes over finite principal ideal rings

The purpose of this paper is to study codes over finite principal ideal rings. To do this, we begin with codes over finite chain rings as a natural generalization of codes over Galois rings GR(p ^e , l) (including ). We give sufficient conditions on the existence of MDS codes over finite chain rings and on the existence of self-dual codes over finite chain rings. We also construct MDS self-dual codes over Galois rings GF(2 ^e , l) of length n = 2 ^l for any a ≥ 1 and l ≥ 2. Torsion codes over residue fields of finite chain rings are introduced, and some of their properties are derived. Finally, we describe MDS codes and self-dual codes over finite principal ideal rings by examining codes over their component chain rings, via a generalized Chinese remainder theorem.      

New approach to nonrepetitive sequences

A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that three symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of three‐element sets L₁,…,L_n there exists a nonrepetitive sequence s₁,…,s_n with s_i∈L_i. We propose a new non‐constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. The simple double counting in the heart of the argument is inspired by the recent algorithmic proof of the Lovász local lemma due to Moser and Tardos. Furthermore we apply this approach and present game‐theoretic type results on nonrepetitive sequences. Nonrepetitive game is played by two players who pick, one by one, consecutive terms of a sequence over a given set of symbols. The first player tries to avoid repetitions, while the second player, in contrast, wants to create them. Of course, by simple imitation, the second player can force lots of repetitions of size 1. However, as proved by Pegden, there is a strategy for the first player to build an arbitrarily long sequence over 37 symbols with no repetitions of size greater than 1. Our techniques allow to reduce 37–6. Another game we consider is the erase‐repetition game. Here, whenever a repetition occurs, the repeated block is immediately erased and the next player to move continues the play. We prove that there is a strategy for the first player to build an arbitrarily long nonrepetitive sequence over 8 symbols. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012