On the Complexity of Partial Order Properties

The recognition complexity of ordered set properties is considered in terms of how many questions must be put to an adversary to decide if an unknown partial order has the prescribed property. We prove a lower bound of order n ² for properties that are characterized by forbidden substructures of fixed size. For the properties being connected, and having exactly k comparable pairs, k n ² / 4 we show that the recognition complexity is (n\choose 2). The complexity of interval orders is exactly (n\choose 2) - 1. We further establish bounds for being a lattice, being of height k and having width k.     

Orthogonal designs II

Orthogonal designs are a natural generalization of the Baumert-Hall arrays which have been used to construct Hadamard matrices. We continue our investigation of these designs and show that orthogonal designs of type (1,k) and ordern exist for everyk < n whenn = 2 ^t+2?3 andn = 2 ^t+2?5 (wheret is a positive integer). We also find orthogonal designs that exist in every order 2n and others that exist in every order 4n. Coupled with some results of earlier work, this means that theweighing matrix conjecture ‘For every ordern ≡ 0 (mod 4) there is, for eachk ?n, a square {0, 1, ? 1} matrixW = W(n, k) satisfyingWW ^t =kIn’ is resolved in the affirmative for all ordersn = 2^t+1?3,n = 2^t+1?5 (t a positive integer). The fact that the matrices we find are skew-symmetric for allk < n whenn ≡ 0 (mod 8) and because of other considerations we pose three other conjectures about weighing matrices having additional structure and resolve these conjectures affirmatively in a few cases. In an appendix we give a table of the known results for orders ? 64.     

Une preuve simple des conjectures de Langlands pour GL(n) sur un corps p-adique

Let F be a finite extension of ℚ _p . For each integer n≥1, we construct a bijection from the set ?_F ⁰ (n) of isomorphism classes of irreducible degree n representations of the (absolute) Weil group of F, onto the set ? _F ⁰ (n) of isomorphism classes of smooth irreducible supercuspidal representations of GL _n (F). Those bijections preserve epsilon factors for pairs and hence we obtain a proof of the Langlands conjectures for GL _n over F, which is more direct than Harris and Taylor’s. Our approach is global, and analogous to the derivation of local class field theory from global class field theory. We start with a result of Kottwitz and Clozel on the good reduction of some Shimura varieties and we use a trick of Harris, who constructs non-Galois automorphic induction in certain cases. Oblatum 1-III-1999 & 21-VII-1999 / Published online: 29 November 1999     

The model theory of m‐ordered differential fields

In his Ph.D. thesis [7], L. van den Dries studied the model theory of fields (more precisely domains) with finitely many orderings and valuations where all open sets according to the topology defined by an order or a valuation is globally dense according with all other orderings and valuations. Van den Dries proved that the theory of these fields is companionable and that the theory of the companion is decidable (see also [8]). In this paper we study the case where the fields are expanded with finitely many orderings and an independent derivation. We show that the theory of these fields still admits a model companion in the language L = {+, –, ·, D, <₁, …, <_m, 1, 0}. We denote this model companion by CODF_m and give a geometric axiomatization of this theory which uses basic notions of algebraic geometry and some generalized open subsets which appear naturally in this context. This axiomatization allows to recover (just by putting m = 1) the one given in [4] for the theory CODF of closed ordered differential fields. Most of the technics we use here are already present in [2] and [4]. Finally, we prove that it is possible to describe the completions of CODF_m and to obtain quantifier elimination in a slightly enriched (infinite) language. This generalizes van den Dries' results in the “derivation free” case. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Constructions of p-ary Quadratic Bent Functions

Bent functions have many applications in the fields of coding theory, communications and cryptography. This paper studies the constructions of bent functions having the form for odd n and for even n, over the finite field of odd characteristic p, where . Based on the irreducibility of some polynomials on , we focus on characterizing the bent functions for n=p ^v q ^r and n=2p ^v q ^r , where is an odd prime and p a primitive root modulo q ². Moreover, the enumerations of those functions are also considered. Partially supported by the NSF of China under Grants No. 60603012 and No. 60573053.     

The Orthogonality Spectrum for Latin Squares of Different Orders

Two orthogonal latin squares of order n have the property that when they are superimposed, each of the n ² ordered pairs of symbols occurs exactly once. In a series of papers, Colbourn, Zhu, and Zhang completely determine the integers r for which there exist a pair of latin squares of order n having exactly r different ordered pairs between them. Here, the same problem is considered for latin squares of different orders n and m. A nontrivial lower bound on r is obtained, and some embedding-based constructions are shown to realize many values of r.     

Dimension pure globale des anneaux commutatifs

For every (n,m) ? IN^?× IN ^?, verifying l We study direct systems of rings and give a bound for the pure - global - dimension of their limits, not depending on the ring cardinality. Using this result and a theorem of C0UCH0T we give examples of pure -heriditary group- rings (ie. of pure -global - dimension one) of large cardinality.

Finaly we prove - using a result of VASC0NCEL0S and a theorem of JENSEN - that some countably products of noetherian rings are coherent rings and that their pure - global - dimension is exactly two.     

Positive integers expressible as a sum of three squares in essentially only one way

The set S consisting of those positive integers n which are uniquely expressible in the form n = a² + b² + c², $\text{a ≧ b ≧ c ≧ 0}$, is considered. Since n ∈ S if and only if 4n ∈ S, we may restrict attention to those n not divisible by 4. Classical formulas and the theorem that there are only finitely many imaginary quadratic fields with given class number imply that there are only finitely many n ∈ S with n = 0 (mod 4). More specifically, from the existing knowledge of all the imaginary quadratic fields with odd discriminant and class number 1 or 2 it is readily deduced that there are precisely twelve positive integers n such that n ∈ S and n ≡ 3 (mod 8). To determine those n ∈ S such that n ≡ 1, 2, 5, 6 (mod 8) requires the determination of the imaginary quadratic fields with even discriminant and class number 1, 2, or 4. While the latter information is known empirically, it has not been proved that the known list of 33 such fields is complete. If it is complete, then our arguments show that there are exactly 21 positive integers n such that n ∈ S and n ≡ 1, 2, 5, 6 (mod 8).     

A census of maximum uniquely hamiltonian graphs

We show that there are 2^[n/2]-4 largest graphs of order n ≥ 7 having exactly one hamiltonian cycle. a recursive procedure for constructing these graphs is described.     

The structure of weighing matrices having large weights

We examine the structure of weighing matricesW(n, w), wherew=n–2,n–3,n–4, obtaining analogues of some useful results known for the casen–1. In this setting we find some natural applications for the theory ofsigned groups and orthogonal matrices with entries from signed groups, as developed in [3]. We construct some new series of Hadamard matrices from weighing matrices, including the following:W(n, n–2) implies an Hadamard matrix of order2n ifn0 mod 4 and order 4n otherwise;W(n, n–3) implies an Hadamard matrix of order 8n; in certain cases,W(n, n–4) implies an Hadamard matrix of order 16n. We explicitly derive 117 new Hadamard matrices of order 2 ^t p, p<4000, the smallest of which is of order 2³·419.Supported by an NSERC grant     

On the Paper "Asymptotics for the Moments of Singular Distributions"

In their 1993 paper, W. Goh and J. Wimp derive interesting asymptotics for the moments c_n(α) ≡ c_n = ∫¹₀tⁿdα(t), N = 0, 1, 2, ..., of some singular distributions α (with support [0, 1]), which contain oscillatory terms. They suspect, that this is a general feature of singular distributions and that this behavior provides a striking contrast with what happens for absolutely continuous distributions. In the present note, however, we give an example of an absolutely continuous measure with asymptotics of moments containing oscillatory terms, and an example of a singular measure having very regular asymptotic behavior of its moments. Finally, we give a short proof of the fact that the drop-off rate of the moments is exactly the local measure dimension about 1 (if it exists).     

On the focus order of planar polynomial differential equations

This paper is devoted to finding the highest possible focus order of planar polynomial differential equations. The results consist of two parts: (i) we explicitly construct a class of concrete systems of degree n, where n+1 is a prime p or a power of a prime pk, and show that these systems can have a focus order n²−n; (ii) we theoretically prove the existence of polynomial systems of degree n having a focus order n²−1 for any even number n. Corresponding results for odd n and more concrete examples having higher focus orders are given too.     

Recognition by spectrum for finite linear groups over fields of characteristic 2

The spectrum of a finite group is the set of its element orders. For every finite simple linear group L = L_n(2^k), where 11 ⩽ n ⩽ 18 or n > 24, we describe finite groups having the same spectrum as L, prove that the number of pairwise nonisomorphic groups with this property is finite, and derive an explicit formula for calculating this number.     

On the differential geometry of frame bundles

Summary The problem to ascertain an admissible structure of frame bundles is solved in this paper, presenting a tensor field H of type-(1.1) which satisfies H³ = H. It acts on the horizontal tensor field as an annihilator and on the vertical tensor field as an almost product structure. When a metric is endowed on the base manifold, it is always possible to assign the metric in the frame bundle such that its element of length obeys the Pythagorean rule when the measurement is done along horizontal and vertical distributions, and by such a general metric it can be proved that the tangent bundle of a frame bundle F(X_n) is reduced to0(n²) ×0(n); especially for n=2m, it is reduced to U(mn) ×0(n). The Lie derivative of H and the parallelism of the three lifts, horizontal, vertical and cnmplete, are examined in terms of their corresponding projection vector fields in the base space.     

Dedekind zeta-functions and Dedekind sums

In this paper we use Dedekind zeta functions of two real quadratic number fields at -1 to denote Dedekind sums of high rank. Our formula is different from that of Siegel’s. As an application, we get a polynomial representation of ζK(-1): ζK(-1) = 1/45(26n³ -41n± 9),n = ±2(mod 5), where K = Q(√5q), prime q = 4n² + 1, and the class number of quadratic number field K2 = Q(vq) is 1.     

Basics of a generalized Wiman–Valiron theory for monogenic Taylor series of finite convergence radius

In this paper, we develop the basic concepts for a generalized Wiman–Valiron theory for Clifford algebra valued functions that satisfy inside an n + 1-dimensional ball the higher dimensional Cauchy-Riemann system ${\frac{\partial f}{\partial x_0} + \sum_{i=1}^n e_i\frac{\partial f}{\partial x_i}=0}In this paper, we develop the basic concepts for a generalized Wiman–Valiron theory for Clifford algebra valued functions that satisfy inside an n + 1-dimensional ball the higher dimensional Cauchy-Riemann system \frac?f?x₀ + ?_i=1ⁿ e_i\frac?f?x_i=0{\frac{\partial f}{\partial x_0} + \sum_{i=1}^n e_i\frac{\partial f}{\partial x_i}=0} . These functions are called monogenic or Clifford holomorphic inside the ball. We introduce growth orders, the maximum term and a generalization of the central index for monogenic Taylor series of finite convergence radius. Our goal is to establish explicit relations between these entities in order to estimate the asymptotic growth behavior of a monogenic function in a ball in terms of its Taylor coefficients. Furthermore, we exhibit a relation between the growth order of such a function f and the growth order of its partial derivatives.     

Investigating the anomaly puzzle in <Emphasis Type="Italic">N</Emphasis>=1 supersymmetric electrodynamics

Using Schwinger-Dyson equations and Ward identities in the N=1 supersymmetric electrodynamics regularized by higher derivatives, we find that we can calculate some contributions to the two-point Greens function of the gauge field and to the -function exactly in all orders of the perturbation theory. We use the results to investigate the anomaly puzzle in the considered theory.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 142, No. 1, pp. 35–56, January, 2005.     

Graphs with exactly one hamiltonian circuit

Let h(n) be the largest integer such that there exists a graph with n vertices having exactly one Hamiltonian circuit and exactly h(n) edges. We prove that h(n) = [n²/4]+1 (n ≧ 4) and discuss some related problems.     

Explicit Geometric Integration of Polynomial Vector Fields

We present a unified framework in which to study splitting methods for polynomial vector fields in R ⁿ . The vector field is to be represented as a sum of shears, each of which can be integrated exactly, and each of which is a function of k<n variables. Each shear must also inherit the structure of the original vector field: we consider Hamiltonian, Poisson, and volume-preserving cases. Each case then leads to the problem of finding an optimal distribution of points on an appropriate homogeneous space, generally the Grassmannians of k-planes or (in the Hamiltonian case) isotropic k-planes in R ⁿ . These optimization problems have the same structure as those of constructing optimal experimental designs in statistics.     

Genre et genre residuel des corps de fonctions values

Let L be a function field of one variable over a valued field (K,|.|), and (|.|_i), 1is, be distinct absolute values over L extending |.| such that the residue fields ¯Lⁱ are function fields of one variable over the residue field ¯K of (K,|.|). We define the defect of the valued function fields (L,|.|_i)/(K,|.|) and prove an inequality between the genus of L/K and that's of ¯Lⁱ/¯K which takes into account the defect, the ramification index of (L,|.|_i)/(K,|.|) and the constant field of Lⁱ/¯K. Our inequality is better than Mathieu's inequality in discretely valued case.