Center conditions III: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). Folowing [7], we consider a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ε ∈ ℂ, is said to have a parametric center, if for any ɛ and for any solutiony(ɛ,x) of (**)y(ɛ, 0)≡y(ɛ, 1).. We give another proof of the fact, shown in [6], that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and generalize a “canonical representation” ofm _k (x) given in [7]. On this base we prove in some additional cases a composition conjecture, stated in [6, 7] for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

On completely free elements in finite fields

Letq>1 be a prime power,m>1 an integer,GF(q ^m) andGF (q) the Galois fields of orderq ^m andq, respectively. We show that the different module structures of (GF(q ^m), +) arising from the intermediate fields of the field extensionGF(q ^m) overGF (q), can be studied simultaneously with the help of some basic properties of cyclotomic polynomials. The results can be generalized to finite cyclic Galois extensions over arbitrary fields.In 1986, D. Blessenohl and K. Johnsen proved that there exist elements inGF(q ^m) which generate normal bases inGF(q ^m) overany intermediate fieldGF(q ^d) ofGF(q ^m) overGF(q). Such elements are called completely free inGF(q ^m) overGF(q). Using our ideas, we give a detailed and constructive proof of the most difficult part of that theorem, i.e., the existence of completely free elements inGF(q ^m), overGF(q) provided thatm is a prime power. The general existence problem of completely free elements is easily reduced to this special case.Furthermore, we develop a recursive formula for the number of completely free elements inGF(q ^m) overGF(q) in the case wherem is a prime power.     

Center conditions II: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). We introduce a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ℂ, is said to have a parametric center, if for any ε and for any solutiony(ε,x) of (**),y(ε,0)≡y(ε,1). We show that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and on this base prove in some special cases a composition conjecture, stated in [10], for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

A New Characterization of Semi-bent and Bent Functions on Finite Fields*

We present a new characterization of semi-bent and bent quadratic functions on finite fields. First, we determine when a GF(2)-linear combination of Gold functions Tr(x²ⁱ+1) is semi-bent over GF(2ⁿ), n odd, by a polynomial GCD computation. By analyzing this GCD condition, we provide simpler characterizations of semi-bent functions. For example, we deduce that all linear combinations of Gold functions give rise to semi-bent functions over GF(2^p) when p belongs to a certain class of primes. Second, we generalize our results to fields GF(pⁿ) where p is an odd prime and n is odd. In that case, we can determine whether a GF(p)-linear combination of Gold functions Tr(x^pi+1) is (generalized) semi-bent or bent by a polynomial GCD computation. Similar to the binary case, simple characterizations of these p-ary semi-bent and bent functions are provided. Parts of this paper were presented at the 2002 IEEE International Symposium on Information Theory [10]     

Taking pth Roots Modulo Polynomials over Finite Fields

In this contribution we show how to find y(x) in the polynomial equation y(x) ^p t(x) mod f(x), where t(x), y(x) and f(x) are polynomials over the field GF(p ^m). The solution of such equations are thought for in many cases, e.g., for p = 2 it is a step in the so-called Patterson Algorithm for decoding binary Goppa codes.     

Optimal broadcast on parallel locality models

In this paper matching upper and lower bounds for broadcast on general purpose parallel computation models that exploit network locality are proven. These models try to capture both the general purpose properties of models like the PRAM or BSP on the one hand, and to exploit network locality of special purpose models like meshes, hypercubes, etc., on the other hand. They do so by charging a cost l(|i−j|) for a communication between processors i and j, where l is a suitably chosen latency function.An upper bound T(p)=∑_i=0^loglogp2ⁱ·l(p^1/2i) on the runtime of a broadcast on a p processor H-PRAM is given, for an arbitrary latency function l(k).The main contribution of the paper is a matching lower bound, holding for all latency functions in the range from l(k)=Ω(logk/loglogk) to l(k)=O(log²k). This is not a severe restriction since for latency functions l(k)=O(logk/log¹⁺log(k)) with arbitrary >0, the runtime of the algorithm matches the trivial lower bound Ω(logp) and for l(k)=Θ(log¹⁺k) or l(k)=Θ(k), the runtime matches the other trivial lower bound Ω(l(p)). Both upper and lower bounds apply for other parallel locality models like Y-PRAM, D-BSP and E-BSP, too.     

A brill - noether theory for<Emphasis Type="Italic">κ</Emphasis>-gonal nodal curves

LetV(g, x, k, y) be the set of all pairs (X, F), whereX is an integral projective nodal curve withp _a(X)=g and card(Sing(X))=x andF is a rank 1 torsion free sheaf onX with deg(F)=k, card(Sing(F))=y andh ⁰(X, F)≥2. Here we study a general (X, F) εV(g, x, k, y) and in particular the Brill-Noether theory ofX and the scrollar invariants ofF.     

Subspaces of<Emphasis Type="Italic">l</Emphasis><Superscript>∞</Superscript> (Γ) without quasicomplements

J. Lindenstrauss proves in [L] thatc ₀(Γ) is not quasicomplemented inl ^∞(Γ) while H. P. Rosenthal in [R] proves that subspaces, whose dual balls are weak* sequentially compact and weak* separable, are quasicomplemented inl ^∞(Γ). In this note it is proved that weak* separability of the dual is the precise condition determining whether a subspace, without isomorphic copies ofl ₁ and whose dual balls are weak* sequentially compact, is quasicomplemented or not inl ^∞(Γ). Especially spaces isomorphic tol _p(Γ), for 1<p<∞, have no quasicomplements inl ^∞(Γ) if Γ is uncountable.     

Diameters of finite upper half plane graphs

Let GF(q) be a finite field of q elements. Let G denote the group of matrices M(x, y) = (^{y x}_{0 1}) over GF(q) with y ≠ 0. Fix an irreducible polynomial For each a ϵ GF(q), let X_a be the graph whose vertices are the q² − q elements of G, with two vertices M(x, y), M(v, w) joined by an edge if and only if The graphs X_a with a ϵ/ {0, t² − 4n} are (q + 1)-regular connected graphs which have received recent attention, as they've been shown to be Ramanujan graphs. We determine the diameter of these graphs X_a. © 1996 John Wiley & Sons, Inc.     

On an Isomorphism Problem of Some Dual Hyperovals in PG(2d + 1, q) with q even

Let q = 2^l with l≥ 1 and d ≥ 2. We prove that any automorphism of the d-dimensional dual hyperoval over GF(q), constructed in [3] for any (d + 1)-dimensional GF(q)-vector subspace V in GF(qⁿ) with n≥ d + 1 and for any generator σ of the Galois group of GF(qⁿ) over GF(q), always fixes the special member X(∞). Moreover, we prove that, in case V = GF(q^d+1), two dual hyperovals and in PG(2d + 1,q), where σ and τ are generators of the Galois group of GF(q^d+1) over GF(q), are isomorphic if and only if (1) σ = τ or (2) σ τ = id. Therefore, we have proved that, even in the case q > 2, there exist non isomorphic d-dimensional dual hyperovals in PG(2d + 1,q) for d ≥ 3.     

Logarithmic derivatives of theta functions

We provide two new proofs of the identity {fx253-1} where °(n)=d ₁(n)−d ₂(n) andd _i (n) is the number of divisors ofn congruent toi mod 3. Furthermore, we express the number of solutions of the Diophantine equationx ²+3y ²=N in terms of δ(N).     

New pairs of -sequences with 4-level cross-correlation

Let ω be a primitive element of GF(2ⁿ), where . Let d=(2^2k+2^s+1-2^k+1-1)/(2^s-1), where n=2k, and s is such that 2s divides k. We prove that the binary m-sequences s(t)=tr(ω^t) and s(dt) have a four-level cross-correlation function and give the distribution of the values.     

Approximation by harmonic functions in theC m -Norm and harmonicC m -capacity of compact sets in ℝ n

We study the function Λ ^m (X), 0<m<1, of compact setsX in ℝ ⁿ , n≥2, defined as the distance in the spaceC ^m (X)≡lip ^m(X) from the function |x|² to the subspaceH ^m (X) which is the closure inC ^m (X) of the class of functions harmonic in the neighborhood ofX (each function in its own neighborhood). We prove the equivalence of the conditions Λ ^m (X)=0 andC ^m (X)=H ^m (X). We derive an estimate from above that depends only on the geometrical properties of the setX (on its volume). Translated fromMatematicheskie Zametki, Vol. 62, No. 3, pp. 372–382, September, 1997. Translated by I. P. Zvyagin     

Multiple Symmetric Solutions for Discrete Lidstone Boundary Value Problems

We offer criteria for the existence of single, double and multiple positive symmetric solutions for the boundary value problem ?^{2m y(k-m)= f(y(k), ?²y(k-1)….,?SUP>2i y(k-i),…,?2(m-1)} y(k-(m-1))), k∈{a+1,…,b+1} ?²ⁱ y(a+1-m)=?²ⁱ y(b+1+m-2i)=0, 0≤i≤m-1 where m ≥ 1 and (-1)^m f can either be positive or the condition can be relaxed.     

Harmonic Analysis on a Galois Field and Its Subfields

Complex functions χ(m) where m belongs to a Galois field GF(p ^ℓ ), are considered. Fourier transforms, displacements in the GF(p ^ℓ )×GF(p ^ℓ ) phase space and symplectic transforms of these functions are studied. It is shown that the formalism inherits many features from the theory of Galois fields. For example, Frobenius transformations and Galois groups are introduced in the present context. The relationship between harmonic analysis on GF(p ^ℓ ) and harmonic analysis on its subfields, is studied.      

Regularization of two-term differential equations with singular coefficients by quasiderivatives

We propose a regularization of the formal differential expression

Some Properties of Bent Functions

First, this paper discusses and sums up some properties of a pair of functions p（x）, q（x） that makes （y ＋ 1）p（x） ＋ yq（x） into a bent function. Then it discusses the properties of bent functions. Also, the upper and lower bounds of the number of bent functions on GF（2）2k are discussed.     

A comparative study of functional equations characterising sine and cosine

A comparative study of the functional equationsf(x+y)f(x–y)=f ²(x)–f ²(y),f(y){f(x+y)+f(x–y)}=f(x)f(2y) andf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} which characterise the sine function has been carried out. The zeros of the functionf satisfying any one of the above equations play a vital role in the investigations. The relation of the equationf(x+y)+f(x–y)=2f(x){1–2f ²(y/2)} with D'Alembert's equation,f(x+y)+f(x–y)=2f(x)f(y) and the sine-cosine equationg(x–y)=g(x)g(y) +f(x)f(y) has also been investigated.