Two-tuple balance of non-binary sequences with ideal two-level autocorrelation

Let p be a prime, q=p^m and F_q be the finite field with q elements. In this paper, we will consider q-ary sequences of period qⁿ-1 for q>2 and study their various balance properties: symbol-balance, difference-balance, and two-tuple-balance properties. The array structure of the sequences is introduced, and various implications between these balance properties and the array structure are proved. Specifically, we prove that if a q-ary sequence of period qⁿ-1 is difference-balanced and has the “cyclic” array structure then it is two-tuple-balanced. We conjecture that a difference-balanced q-ary sequence of period qⁿ-1 must have the cyclic array structure. The conjecture is confirmed with respect to all of the known q-ary sequences which are difference-balanced, in particular, which have the ideal two-level autocorrelation function when q=p.     

New Cyclic Difference Sets with Singer Parameters Constructed from d-Homogeneous Functions

In this paper, for a prime power q, new cyclic difference sets with Singer para- meters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed by using q-ary sequences (d-homogeneous functions) of period q ⁿ –1 and the generalization of GMW difference sets is proposed by combining the generation methods of d-form sequences and extended sequences. When q is a power of 3, new cyclic difference sets with Singer parameters ((q ⁿ –1/q–1), (q ^n–1–1/q–1), (q ^n–2–1/q–1)) are constructed from the ternary sequences of period q ⁿ –1 with ideal autocorrelation introduced by Helleseth, Kumar, and Martinsen.     

The existence of (p,q)-extended Rosa sequences

A (p,q)-extended Rosa sequence is a sequence of length 2n+2 containing each of the symbols 0,1,…,n exactly twice, and such that two occurrences of the integer j>0 are separated by exactly j-1 symbols. We prove that, with two exceptions, the conditions necessary for the existence of a (p,q)-extended Rosa sequence with prescribed positions of the symbols 0 are sufficient. We also extend the result to λ-fold (p,q)-extended Rosa sequences; i.e., the sequences where every pair of numbers is repeated exactly λ times.     

Odd prime values of the Ramanujan tau function

We study the odd prime values of the Ramanujan tau function, which form a thin set of large primes. To this end, we define LR(p,n):=τ(p ^n?1) and we show that the odd prime values are of the form LR(p,q) where p,q are odd primes. Then we exhibit arithmetical properties and congruences of the LR numbers using more general results on Lucas sequences. Finally, we propose estimations and discuss numerical results on pairs (p,q) for which LR(p,q) is prime.     

On the asymptotic existence of cocyclic Hadamard matrices

Let q be an odd natural number. We prove there is a cocyclic Hadamard matrix of order ²10+tq whenever . We also show that if the binary expansion of q contains N ones, then there is a cocyclic Hadamard matrix of order ²4N−2q.     

Tightening Turyn’s bound for Hadamard difference sets

This work examines the existence of (4q ²,2q ²−q,q ²−q) difference sets, for q=p ^f , where p is a prime and f is a positive integer. Suppose that G is a group of order 4q ² which has a normal subgroup K of order q such that G/K ≅ C _q ×C ₂×C ₂, where C _q ,C ₂ are the cyclic groups of order q and 2 respectively. Under the assumption that p is greater than or equal to 5, this work shows that G does not admit (4q ²,2q ²−q,q ²−q) difference sets.     

Note on Periodic Complementary Sets of Binary Sequences

Denote by $PCS_p^n $ resp. $ACS_p^n $ thecollection consisting of ordered p-tuples of binary sequences(i.e., sequences whose elements are $ \pm 1$ ), each having length n, such that the sum of their periodic resp. aperiodicauto-correlation functions is a delta function. We fill many open cases inthe Bömer and Antweiler diagram [3] of the known cases where $PCS_p^n $ exist for $p \leqslant 12$ and $n \leqslant 50$ . In particular we show that $PCS_2^{34} $ exist, whileit is well known [1] that $ACS_2^{34} $ do not.     

Characterization and recognition of generalized clique-Helly graphs

Let p?1 and q?0 be integers. A family of sets F is (p,q)-intersecting when every subfamily F^′⊆F formed by p or less members has total intersection of cardinality at least q. A family of sets F is (p,q)-Helly when every (p,q)-intersecting subfamily F^′⊆F has total intersection of cardinality at least q. A graph G is a (p,q)-clique-Helly graph when its family of (maximal) cliques is (p,q)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case p=2,q=1. In this work we present a characterization for (p,q)-clique-Helly graphs. For fixed p,q, this characterization leads to a polynomial-time recognition algorithm. When p or q is not fixed, it is shown that the recognition of (p,q)-clique-Helly graphs is NP-hard.     

Class number one quadratic fields and solvability of some Pellian equations

Consider these two types of positive square-free integers d≠ 1 for which the class number h of the quadratic field Q(√d) is odd: (1) d is prime∈ 1(mod 8), or d=2q where q is prime ≡ 3 (mod 4), or d=qr where q and r are primes such that q≡ 3 (mod 8) and r≡ 7 (mod 8); (2) d is prime ≡ 1 (mod 8), or d=qr where q and r are primes such that q≡r≡ 3 or 7 (mod 8). For d of type (2) (resp. (1)), let Π be the set of all primes (resp. odd primes) p∈N satisfying (d/p) = 1. Also, let δ :=0 (resp. δ :=1) if d≡ 2,3 (mod 4) (resp. d≡ 1 (mod 4)). Then the following are equivalent: (a) h=1; (b) For every p∈П at least one of the two Pellian equations Z ²-dY ² = ±4^δ p is solvable in integers. (c) For every p∈П the Pellian equation W ²-dV ² = 4^δ p ² has a solution (w,v) in integers such that gcd (w,v) divides 2^δ.     

Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph.     

COMPSTAT '78: 3rd Symposium on computational statistics

It is proved that there are no nontrivial perfect (e,n,q)-codesif e?3 and q = p^r₁p¹₂ where p₁ and p₂ are distinct primes and r and s are positive integers.     

A New Method for Constructing Williamson Matrices

For every prime power q 1 (mod 4) we prove the existence of (q; x, y)-partitions of GF(q) with q=x²+4y² for some x, y, which are very useful for constructing SDS, DS and Hadamard matrices. We discuss the transformations of (q; x,y)-partitions and, by using the partitions, construct generalized cyclotomic classes which have properties similar to those of classical cyclotomic classes. Thus we provide a new construction for Williamson matrices of order q².The research supported by NSF of China (No. 10071029).     

Brauer characters with cyclotomic field of values

It has been shown in an earlier paper [G. Navarro, Pham Huu Tiep, Rational Brauer characters, Math. Ann. 335 (2006) 675-686] that, for any odd prime p, every finite group of even order has a non-trivial rational-valued irreducible p-Brauer character. For p=2 this statement is no longer true. In this paper we determine the possible non-abelian composition factors of finite groups without non-trivial rational-valued irreducible 2-Brauer characters. We also prove that, if p≠q are primes, then any finite group of order divisible by q has a non-trivial irreducible p-Brauer character with values in the cyclotomic field Q(exp(2πi/q)).     

Valency seven symmetric graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is said to be symmetric if its automorphism group acts transitively on its arcs. In this paper, all connected valency seven symmetric graphs of order 2pq are classified, where p, q are distinct primes. It follows from the classification that there is a unique connected valency seven symmetric graph of order 4p, and that for odd primes p and q, there is an infinite family of connected valency seven one-regular graphs of order 2pq with solvable automorphism groups, and there are four sporadic ones with nonsolvable automorphism groups, which is 1, 2, 3-arc transitive, respectively. In particular, one of the four sporadic ones is primitive, and the other two of the four sporadic ones are bi-primitive.     

Character sums over shifted primes

We obtain a new bound for sums of a multiplicative character modulo an integer q at shifted primes p + a over primes p ≤ N. Our bound is nontrivial starting with N ≥ q ^8/9+? for any ? > 0. This extends the range of the bound of Z. Kh. Rakhmonov that is nontrivial for N ≥ q ^1+? .     

On the k-error linear complexity of sequences with period 2pn over GF(q)

In this paper, we first optimize the structure of the Wei–Xiao–Chen algorithm for the linear complexity of sequences over GF(q) with period N =  2p ⁿ , where p and q are odd primes, and q is a primitive root modulo p ². The second, an union cost is proposed, so that an efficient algorithm for computing the k-error linear complexity of a sequence with period 2p ⁿ over GF(q) is derived, where p and q are odd primes, and q is a primitive root modulo p ². The third, we give a validity of the proposed algorithm, and also prove that there exists an error sequence e ^N , where the Hamming weight of e ^N is not greater than k, such that the linear complexity of (s + e) ^N reaches the k-error linear complexity c. We also present a numerical example to illustrate the algorithm. Finally, we present the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.     

Tetravalent edge-transitive graphs of order p 2 q

A graph is called edge-transitive if its full automorphism group acts transitively on its edge set.In this paper,by using classification of finite simple groups,we classify tetravalent edge-transitive graphs of order p2q with p,q distinct odd primes.The result generalizes certain previous results.In particular,it shows that such graphs are normal Cayley graphs with only a few exceptions of small orders.     

Metrical Theorems on Restricted Diophantine Approximations to Points on a Curve

We investigate rational approximations (r/p,q/p) or (r/p,q/r) to points on the curve (α,α^τ) for almost all α>0, where p,q,r are all primes. We immediately obtain corollaries on making p,[αp], [α^τp] simultaneously prime.     

Correlation measure,linear complexity and maximum order complexity for families of binary sequences

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.