Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Elementary proof of the transformation formula for Lambert series involving generalized Dedekind sums

An elementary proof is given of the author's transformation formula for the Lambert series $\text{G}{}_{\mathrm{p}}\text{(x) =}\text{Σ}{}_{\mathrm{n?1}}{}^{\mathrm{<mtext>\infty </mtext>}}\text{n}{}^{\mathrm{?p}}\text{x}{}^{\mathrm{n}}\text{(1?x}{}^{\mathrm{n}}\text{)}$ relating G_p(e^2πiτ) to G_p(e^2πiAτ), where p > 1 is an odd integer and $\text{Aτ =}\text{(aτ + b)}\text{(cτ + d)}$ is a general modular substitution. The method extends Sczech's argument for treating Dedekind's function $\text{log}\text{η(τ) =}\text{πiτ}\text{12}\text{? G}{}_1\text{(e}{}^{\mathrm{2\pi i\tau }}\text{)}$, and uses Carlitz's formula expressing generalized Dedekind sums in terms of Eulerian functions.     

Diagonal forms over finite fields

We shall establish for all finite fields GF(pⁿ) the following result of Chowla: given a positive integer m greater than one and the finite field GF(p), p a prime, such that x^m = ?1 is solvable in GF(p), then there exists an absolute positive constant c, $\text{c ≤}\text{10}\text{ln}\text{2}$, such that for each set of s nonzero elements a_i of GF(p), $\text{a}{}_1\text{x}{}_1{}^{\mathrm{m}}\text{+ ? + a}{}_{\mathrm{s}}\text{x}{}_{\mathrm{s}}{}^{\mathrm{m}}$ has a non-trivial zero in GF(p) if s ≥ c ln m.     

Scalar polynomial functions on the n×n matrices over a finite field

Let F=GF(q) denote the finite field of order q, and let $\text{?(x)?F[x]}$. Then f(x) defines, via substitution, a function from F_n×n, the n×n matrices over F, to itself. Any function $\text{?:F}{}_{\mathrm{n\times n}}\text{→ F}{}_{\mathrm{n\times n}}$ which can be represented by a polynomialf(x)?F[x] is called a scalar polynomial function on F_n×n. After first determining the number of scalar polynomial functions on F_n×n, the authors find necessary and sufficient conditions on a polynomial $\text{?(x) ? F[x]}$ in order that it defines a permutation of (i) $\text{D}$_n, the diagonalizable matrices in F_n×n, (ii)$\text{R}$_n, the matrices in F_n×n all of whose roots are in F, and (iii) the matric ring F_n×n itself. The results for (i) and (ii) are valid for an arbitrary field F.     

On finite differences,permutations, and Quadratic residues

Let p be an odd prime and n an integer relatively prime to p. In this work three criteria which give the value of the Legendre symbol ($\text{n}\text{p}$) are developed. The first uses two adjacent rows of Pascal's triangle which depend only on p to express ($\text{n}\text{p}$) explicitly in terms of the numerically least residues (mod p) of the numbers n, 2n, …, [$\text{(p + 1)}\text{4}\text{]n}$ or of the numbers $\text{[}\text{(p + 1)}\text{4}\text{]n,…, [}\text{(p ? 1)}\text{2}\text{]n}$. The second, analogous to a theorem of Zolotareff and valid only if p ≡ 1 (mod 4), expresses ($\text{n}\text{p}$) in terms of the parity of the permutation of the set {$\text{1,2,…, (}\text{(p? 1)}\text{2}$} defined by the absolute values of the numerically least residues of $\text{n, 2n,…,[}\text{(p? 1}\text{2}\text{]n}$. The third is a result dual to Gauss' lemma which can be derived directly without Euler's criterion. The applications of the dual include a proof of Gauss' lemma free of Euler's criterion and a proof of the Quadratic Reciprocity Law.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

On the analytic continuation of a certain Dirichlet series

A Dirichlet series associated with a positive definite form of degree δ in n variables is defined by

$\text{D}{}_{\mathrm{F}}\text{(s,p,α)}\text{=}\text{∑}\text{α∈Z}{}^{\mathrm{n}}\text{?{0}}\text{F(α)}{}^{\mathrm{?s}}\text{e(ρF(α)+〈α, α〉)}$

where ? ∈ $\text{Q}$, α ∈ $\text{Q}$ⁿ, 〈x, y〉 = x₁y₁ + ? + x_ny_n, e(a) = exp (2πia) for a ∈ $\text{R}$, and s = σ + ti is a complex number. The author proves that: (1) D_F(s, ?, α) has analytic continuation into the whole s-plane, (2) D_F(s, ?, α), ? ≠ 0, is a meromorphic function with at most a simple pole at $\text{s =}\text{n}\text{δ}$. The residue at $\text{s =}\text{n}\text{δ}$ is given explicitly. (3) ? = 0, α ? $\text{Z}$ⁿ, D_F(s, 0, α) is analytic for $\text{α>,}\text{n}\text{(δ ? 1)}$.     

The lattice of subfields of a radical extension

Let x^m ? a be irreducible over F with char $\text{F?m}$ and let α be a root of x^m ? a. The purpose of this paper is to study the lattice of subfields of $\text{F(α)}\text{F}$ and to this end $\text{C(}\text{F(α)}\text{F}\text{, k)}$ is defined to be the number of subfields of F(α) of degree k over $\text{F. C(}\text{F(α)}\text{F}\text{, p}{}^{\mathrm{n}}\text{)}$ is explicitly determined for p a prime and the following structure theorem for the lattice of subfields is proved. Let N be the maximal normal subfield of F(α) over F and set n = |N : F|, then $\text{C(}\text{F(α)}\text{F}\text{, k) = C(}\text{F(α)}\text{F}\text{, (k, n)) = C(}\text{N}\text{F}\text{, (k, n))}$. The irreducible binomials x^s ? b, x^s ? c are said to be equivalent if there exist roots β^s = b, γ^s = a such that F(β) = F(γ). All the mutually inequivalent binomials which have roots in F(α) are determined. Finally these results are applied to the study of normal binomials and those irreducible binomials x^2e ? a which are normal over F (char F ≠ 2) together with their Galois groups are characterized.     

Corresponding residue systems in normal extensions

Let K and K′ be number fields with L = K · K′ and F = KφK′. Suppose that $\text{K}\text{F}$ and $\text{K′}\text{F}$ are normal extensions of degree n. Let $\text{B}$ be a prime ideal in L and suppose that $\text{B}$ is totally ramified in $\text{K}\text{F}$ and in $\text{K′}\text{F}$. Let π be a prime element for $\text{B}$_K = $\text{B}$ φ K, and let f(x) ∈ F[x] be the minimum polynomial for π over F. Suppose that $\text{B}$_K · $\text{D}$_L = ($\text{B}$^≠)^e. Then,

$\text{M(B\# : K, K′) =}\text{min}\text{{m, e(t + 1)}}$

, where $\text{t =}\text{min}\text{{t(}\text{K}\text{F}\text{), t(}\text{K′}\text{F}\text{)}}$ and m is the largest integer such that ($\text{B}$_K′)^nm/e φ f($\text{D}$_K′) ≠ {φ}.If we assume in addition to the above hypotheses that [K : F] = [K′: F] = pⁿ, a prime power, and that $\text{B}$ divides p and is totally ramified in $\text{L}\text{F}$, then

$\text{M(B\# : K, K′) ? p}{}^{\mathrm{n?1}}\text{[(p ? 1)(t + p]}$

, with t = t($\text{B}$ : L/F).     

Some results on sperner families

Let F be a Sperner family of subsets of {1,…,m}. Bollobás showed that if $\text{A ∈ F ?}\text{A}\text{= {1,…,m}βA ∈ F}$, and if the parameters of F are p₀,…,p_m then

$\text{∑}\text{i=0}\text{[}\text{m}\text{2}\text{Pi}\text{m?1}\text{i?1}\text{+}\text{∑}\text{i=[}\text{m}\text{2}\text{]+1}\text{m}\text{Pi}\text{m?1}\text{m?i?1}\text{? 2}$

Here we generalize this result and prove some analogues of it. A corollary of Bollobás' result is that $\text{|F| ? 2(}{}_{\mathrm{<mtext>[</mtext><mtext>m</mtext><mtext>2</mtext><mtext>]?1</mtext>}}{}^{\mathrm{m?1}}\text{)}$. Purdy proved that if $\text{A ∈ F ?}\text{A}\text{? F}$ then $\text{|F| ? (}{}_{\mathrm{<mtext>[</mtext><mtext>m</mtext><mtext>2</mtext><mtext>]+1</mtext>}}{}^{\mathrm{m}}\text{)}$, which implies Bollobás' corollary. We also show that Purdy's result may be deduced from Bollobás' by a short argument. Finally, we give a canonical form for Sperner families which are also pairwise intersecting.     

Sur une loi de probabilite conditionelle de kleitman

Nous donnons une généralisation et une démonstration très courte d'un théorème de Kleitman qui dit: Pour toute paire d'idéaux $\text{F}$, (β) d'éléments dans le produit cartésien de k ensembles totalement ordonnés P = [1, 2, … n₁] ? … ? [1, 2, … n_k], nous avons ($\text{|}\text{F}\text{|}\text{|P|}$). ($\text{|(β)|}\text{|P|}\text{) ?}\text{|}\text{F}\text{∩ (β)|}\text{|P|}$ ou en langage probabiliste $\text{Pr(}\text{F}\text{? Pr (}\text{F}\text{|(β))}$.     

Finitely generated submodules of differentiable functions II

Let [$\text{E}$(Ω)]^p be the Cartesian product of the space of real-valued infinitely differentiable functions on a connected open set Ω in $\text{R}$ⁿ with itself p-times. The finitely generated submodules of [$\text{E}$(Ω)]^p are of the form im(F) where F: [$\text{E}$(Ω)]^q → [$\text{E}$(Ω)]^p is a p × q matrix of infinitely differentiable functions on Ω. Let $\text{r =}\text{max}\text{{}\text{rank}\text{(F(x)): x ? Ω}}$. The main results of the present paper are that for Ω ? $\text{R}$ⁿ, if the finitely generated submodule im(F) is closed in [$\text{E}$(Ω)]^p, then for every x?ω with rank(F(x)) < r there exists an r × r sub-matrix A of F such that x is a zero of finite order of det(A), and for Ω ? $\text{R}$¹ the converse also holds.     

Maximum zero strings of Bell numbers modulo primes

For any prime p, the sequence of Bell exponential numbers B_n is shown to have p ? 1 consecutive values congruent to zero (mod p), beginning with B_m, where $\text{m ≡ 1 ?}\text{(p}{}^{\mathrm{p}}\text{? 1)}\text{(p ? 1)}{}^2$ ($\text{mod}\text{(p}{}^{\mathrm{p}}\text{? 1)}\text{(p ? 1)}$). This is an improvement over previous results on the maximal strings of zero residues of the Bell numbers. Similar results are obtained for the sequence of generalized Bell numbers A_n generated by .     

Characterization of quadratic and cubic σ-polynomials

Here quadratic and cubic σ-polynomials are characterized, or, equivalently, chromatic polynomials of the graphs of order p, whose chromatic number is p ? 2 or p ? 3, are characterized. Also Robert Korfhage's conjecture that if σ² + bσ + a is a σ-polynomial then $\text{a ≤}\text{1}\text{2}\text{(b}{}^2\text{? 5b + 12)}$ is verified. In general, if σ(G) = Σ₀ⁿa_iσⁱ is a σ-polynomial of a graph G, then a_n?2 is determined.     

A global genericity theorem for bifurcations in variational problems

Let C be a Banach space, H a Hilbert space, and let F(C,H) be the space of C^∞ functions f: C × H → R having Fredholm second derivative with respect to x at each (c, x) ?C × H for which $\text{D?}{}_{\mathrm{c}}\text{(x) = 0}$; here we write $\text{?}{}_{\mathrm{c}}\text{(x)}$ for $\text{?(c, x)}$. Say ? is of standard type if at all critical points of ?_c it is locally equivalent (as an unfolding) to a quadratic form Q plus an elementary catastrophe on the kernel of Q. It is proved that if f?F (A × B, H) satisfies a certain ‘general position’ condition, and dim B ? 5, then for most a?A the function f_o?F(B,H) is of standard type. Using this it is shown that those f?F(B,H) of standard type form an open dense set in F(B,H) with the Whitney topology. Thus both results are Hilbert-space versions of Thom's theorem for catastrophes in $\text{R}$ⁿ.     

Sharp nonlogarithmic Kneser theorems for fourth-order elliptic equations

Let D(?) be the Doob's class containing all functions f(z) analytic in the unit disk Δ such that f(0) = 0 and lim $\text{inf}\text{¦f(z) ¦ ? 1}$ on an arc A of ?Δ with length $\text{¦A ¦? ?}$. It is first proved that if f?D(?) then the spherical norm ∥ f ∥ = sup_z?Δ$\text{(}\text{1 ? ¦z¦}{}^2\text{)¦f′(z)¦}\text{(1 + ¦f(z)¦}{}^2\text{) ? C}{}_1\text{sin}\text{(π ? (}\text{?}\text{2}\text{))/ (π ? (}\text{g9}\text{2}\text{))}$, where C₁ = lim_n→∞$\text{∥ z}{}^{\mathrm{n}}\text{∥}\text{and}\text{1}\text{2}\text{< C}{}_1\text{<}\text{2}\text{e}$. Next, U represents the Seidel's class containing all non-constant functions f(z) bounded analytic in Δ such that $\text{¦tf(e}{}^{\mathrm{i0}}\text{)¦ = 1}$ almost everywhere. It is proved that inf_f?U∥f∥ = 0, and if f has either no singularities or only isolated singularities on ?Δ, then ∥f∥ ? C₁. Finally, it is proved that if f is a function normal in Δ, namely, the norm ∥f∥< ∞, then we have the sharp estimate ∥f^p∥ ? p∥f∥, for any positive integer p.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

On the separation power and the completion of partial latin squares

Let n and m be natural numbers, n ? m. The separation power of order n and degree m is the largest integer k = k(n, m) such that for every (0, 1)-matrix A of order n with constant linesums equal to m and any set of k 1's in A there exist (disjoint) permutation matrices P₁,…, P_m such that A = P₁ + … + P_m and each of the k 1's lies in a different P_i. Almost immediately we have 1 ? k(n, m) ? m ? 1, yet in all cases where the value of k(n, m) is actually known it equals m ? 1 (except under the somewhat trivial circumstances of k(n, m) = 1). This leads to a conjecture about the separation power, namely that k(n, m) = m ? 1 if $\text{m ? [}\text{n}\text{2}\text{] + 1}$. We obtain the bound $\text{k(n, m) ? m ? [}\text{n}\text{2}\text{] + 2}$, so that this conjecture holds for n ? 7. We then move on to latin squares, describing several equivalent formulations of the concept. After establishing a sufficient condition for the completion of a partial latin square in terms of the separation power, we can show that the Evans conjecture follows from this conjecture about the separation power. Finally the lower bound on k(n, m) allows us to show, after some calculations, that the Evans conjecture is true for orders n ? 11.     

Linear transformations on matrices: the invariance of generalized permutation matrices—III

Let F be a field, F1 be its multiplicative group, and $\text{H}$ = {H:H is a subgroup of F1 and there do not exist a, b?F1 such that Ha+b?H}. Let D_n be the dihedral group of degree n, H be a nontrivial group in $\text{H}$, and τ_n(H) = {α = (α₁, α₂,…, α_n):α_i?H}. For σ?D_n and α?τ_n(H), let P(σ, α) be the matrix whose (i,j) entry is α_iδ_iσ(j) (i.e., a generalized permutation matrix), and

$\text{P(D}{}_{\mathrm{n}}\text{, H) = {P(σ, α):σ?D}{}_{\mathrm{n}}\text{, α?τ}{}_{\mathrm{n}}\text{(H)}}$

. Let M_n(F) be the vector space of all n×n matrices over F and $\text{T}$P(D_n, H) = {T:T is a linear transformation on M_n (F) to itself and T(P(D_n, H)) = P(D_n, H)}. In this paper we classify all T in $\text{T}$P(D_n, H) and determine the structure of the group $\text{T}$P(D_n, H) (Theorems 1 to 4). An expository version of the main results is given in Sec. 1, and an example is given at the end of the paper.     

Minimal codes in abelian group algebras

In this paper we show that two minimal codes $\text{M}$₁ and $\text{M}$₂ in the group algebra $\text{F}$₂[G] have the same (Hamming) weight distribution if and only if there exists an automorphism θ of G whose linear extension to $\text{F}$₂[G] maps $\text{M}$₁ onto $\text{M}$₂. If θ(M₁) = M₂, then $\text{M}$₁ and $\text{M}$₂ are called equivalent. We also show that there are exactly τ(l) inequivalent minimal codes in $\text{F}$₂[G], where ? is the exponent of G, and τ(?) is the number of divisors of ?.