On representing sylvester-gallai designs

A misstated conjecture in [3] leads to an interesting (1, 3) representation of the 7-point projective plane inR ⁴ where points are represented by lines and planes by 3-spaces. The corrected form of the original conjecture will be negated if there is a (1, 3) representation of the 13-point projective plane inR ⁴ but that matter is not settled.     

Involutions and linear systems on holomorphic symplectic manifolds

A K3 surface with an ample divisor of self-intersection 2 is a double cover of the plane branched over a sextic curve. We conjecture that similar statement holds for the generic couple (X, H) with X a deformation of (K3)^[n] and H an ample divisor of square 2 for Beauville’s quadratic form. If n = 2 then according to the conjecture X is a double cover of a singular) sextic 4-fold in It follows from the conjecture that a deformation of (K3)^[n] carrying a divisor (not necessarily ample) of degree 2 has an anti-symplectic birational involution. We test the conjecture. In doing so we bump into some interesting geometry: examples of two antisymplectic involutions generating an interesting dynamical system, a case Strange duality and what is probably an involution on the moduli space degree-2 quasi-polarized (X, H) where X is a deformation of (K3)^[2]. Received: June 2004 Revision: December 2004 Accepted: January 2005     

Saddle points and overdetermined problems for the Helmholtz equation

In a seminal 1971 paper, James Serrin showed that the only open, smoothly bounded domain in ⁿ on which the positive Dirichlet eigenfunction of the Laplacian has constant (nonzero) normal derivative on the boundary, is then-dimensional ball. The positivity of the eigenfunction is crucial to his proof. To date it is an open conjecture that the same result is true for Dirichlet eigenvalues other than the least. We show that for simply connected, plane domains, the absence of saddle points is a condition sufficient to validate this conjecture. This condition is also sufficient to prove Schiffer's conjecture: the only simply connected planar domain, on the boundary of which a nonconstant Neumann eigenfunction of the Laplacian can take constant value, is the disc.     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

Dimension versus size

We investigate the behavior of f(d), the least size of a lattice of order dimension d. In particular we show that the lattice of a projective plane of order n has dimension at least n/ln(n), so that f(d)=O(d) ² log² d. We conjecture f(d)=(d ² ), and prove something close to this for height-3 lattices, but in general we do not even know whether f(d)/d.Supported in part by NSF grant MCS 83-01867, AFORS grant number 0271 and a Sloan Research Fellowship.     

Flag transitive planes of orderq n with a long cyclel ∞ as a collineation

Baker and Ebert [1] presented a method for constructing all flag transitive affine planes of orderq ² havingGF(q) in their kernels for any odd prime powerq. Kantor [6; 7; 8] constructed many classes of nondesarguesian flag transitive affine planes of even order, each admitting a collineation, transitively permuting the points at infinity. In this paper, two classes of non-desarguesian flag transitive affine planes of odd order are constructed. One is a class of planes of orderq ⁿ , whereq is an odd prime power andn 3 such thatq ⁿ 1 (mod 4), havingGF(q) in their kernels. The other is a class of planes of orderq ⁿ , whereq is an odd prime power andn 2 such thatq ⁿ 1 (mod 4), havingGF(q) in their kernels. Since each plane of the former class is of odd dimension over its kernel, it is not isomorphic to any plane constructed by Baker and Ebert [1]. The former class contains a flag transitive affine plane of order 27 constructed by Kuppuswamy Rao and Narayana Rao [9]. Any plane of the latter class of orderq ⁿ such thatn 1 (mod 2), is not isomorphic to any plane constructed by Baker ad Ebert [1].The author is grateful to the referee for many helpful comments.     

The Steiner ratio conjecture for cocircular points

A Steiner minimal treeS is a network of shortest possible length connecting a set ofn points in the plane. LetT be a shortest tree connecting then points but with vertices only at these points.T is called a minimal spanning tree. The Steiner ratio conjecture is that the length ofS divided by the length ofT is at least 3/2. In this paper we use a variational approach to show that if then points lie on a circle, then the Steiner ratio conjecture holds.     

From the Mahler Conjecture to Gauss Linking Integrals

We establish a version of the bottleneck conjecture, which in turn implies a partial solution to the Mahler conjecture on the product v(K)  = (Vol K)(Vol K°) of the volume of a symmetric convex body and its polar body K°. The Mahler conjecture asserts that the Mahler volume v(K) is minimized (non-uniquely) when K is an n-cube. The bottleneck conjecture (in its least general form) asserts that the volume of a certain domain is minimized when K is an ellipsoid. It implies the Mahler conjecture up to a factor of (π/4) ⁿ γ _n , where γ _n is a monotonic factor that begins at 4/π and converges to . This strengthens a result of Bourgain and Milman, who showed that there is a constant c such that the Mahler conjecture is true up to a factor of c ⁿ . The proof uses a version of the Gauss linking integral to obtain a constant lower bound on Vol K ^◇, with equality when K is an ellipsoid. It applies to a more general conjecture concerning the join of any two necks of the pseudospheres of an indefinite inner product space. Because the calculations are similar, we will also analyze traditional Gauss linking integrals in the sphere S ^n-1 and in hyperbolic space H ^n-1. Received: December 2006, Accepted: January 2007     

Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems

Summary This paper deals with rational functions ø(z) approximating the exponential function exp(z) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the greatest nonnegative numberR, denoted byR(ø), such that ø is absolutely monotonic on (–R, 0]. An algorithm for the computation ofR(ø) is presented. Application of this algorithm yields the valueR(ø) for the well-known Padé approximations to exp(z). For some specific values ofm, n andp we determine the maximum ofR(ø) when ø varies over the class of all rational functions ø with degree of the numerator m, degree of the denominator n and ø(z)=exp(z)+(z ^p+1 ) (forz0).     

A combinatorial approach for Keller's conjecture

The statement, that in a tiling by translates of ann-dimensional cube there are two cubes having common (n-1)-dimensional faces, is known as Keller's conjecture. We shall prove that there is a counterexample for this conjecture if and only if the following graphs _n has a 2 ⁿ size clique. The 4 ⁿ vertices of _n aren-tuples of integers 0, 1, 2, and 3. A pair of thesen-tuples are adjacent if there is a position at which the difference of the corresponding components is 2 modulo 4 and if there is a further position at which the corresponding components are different. We will give the size of the maximal cliques of _n forn5.     

Colorings Of Plane Graphs With No Rainbow Faces

We prove that each n-vertex plane graph with girth g≥4 admits a vertex coloring with at least ⌈n/2⌉+1 colors with no rainbow face, i.e., a face in which all vertices receive distinct colors. This proves a conjecture of Ramamurthi and West. Moreover, we prove for plane graph with girth g≥5 that there is a vertex coloring with at least if g is odd and if g is even. The bounds are tight for all pairs of n and g with g≥4 and n≥5g/2−3. * Supported in part by the Ministry of Science and Technology of Slovenia, Research Project Z1-3129 and by a postdoctoral fellowship of PIMS. ** Institute for Theoretical Computer Science is supported by Ministry of Education of CzechR epublic as project LN00A056.     

Codimension 2 subvarieties of projective space

The motivation for the present paper is theHartshorne Conjecture on complete intersections inP ⁿ , forn6, and in the codimension 2 case: Any smooth codimension 2 subvarietyX ofP ⁿ is conjectured to be a complete intersection forn6. We prove this conjecture for all varieties with degree below a certain bound, which represents an improvement of the numerical information available untill now.This research has been supported by a grant from theStefi andLars Fylkesaker Foundation     

On a Problem of Fabrykowski and Subbarao Concerning Quasi Multiplicative Functions Satisfying a Congruence Property

It follows from our result that if a quasi multiplicative function f satisfies the congruence f(n + p) f(n) (mod p) for all positive integers n and for all sufficiently large primes p, then there is a non-negative integer such that f(n) = n holds for all positive integers n. In particular, this gives an answer to the conjecture of Fabrykowski and Subbarao.     

Exact solution of linear equations usingP-adic expansions

Summary A method is described for computing the exact rational solution to a regular systemAx=b of linear equations with integer coefficients. The method involves: (i) computing the inverse (modp) ofA for some primep; (ii) using successive refinements to compute an integer vector such that (modp ^m ) for a suitably large integerm; and (iii) deducing the rational solutionx from thep-adic approximation . For matricesA andb with entries of bounded size and dimensionsn×n andn×1, this method can be implemented in timeO(n ³(logn)²) which is better than methods previously used.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (Grant No. A 7171)     

On the distribution of comparisons in sorting algorithms

We considered the following natural conjecture: For every sorting algorithm every key will be involved in(logn) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involven–n /2+1 keys in at leastlog₂ n comparisons,>0. Further, there exists a sorting algorithm that will for every input involve at mostn–n ^/c keys in greater thanlog₂ n comparisons, wherec is a constant and>0. The conjecture is shown to hold for natural algorithms from the literature.     

On Heilbronn’s Problem in Higher Dimension

Heilbronn conjectured that given arbitrary n points in the 2-dimensional unit square [0, 1]², there must be three points which form a triangle of area at most O(1/n²). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz and Szemerédi [10] who showed that for every n there is a configuration of n points in the unit square [0, 1]² where all triangles have area at least (log n/n²). Considering a generalization of this problem to dimensions d3, Barequet [3] showed for every n the existence of n points in the d-dimensional unit cube [0, 1]^d such that the minimum volume of every simplex spanned by any (d+1) of these n points is at least (1/n^d). We improve on this lower bound by a logarithmic factor (log n).     

On the spectrum of resolvable orthogonal arrays invariant under the Klein group K4

It is shown that there exists a resolvablen ² by 4 orthogonal array which is invariant under the Klein 4-groupK ₄ for all positive integersn congruent to 0 modulo 4 except possibly forn {12, 24, 156, 348}.     

On the number of halving planes

LetS ³ be ann-set in general position. A plane containing three of the points is called a halving plane if it dissectsS into two parts of equal cardinality. It is proved that the number of halving planes is at mostO(n ^2.998).As a main tool, for every setY ofn points in the plane a setN of sizeO(n ⁴) is constructed such that the points ofN are distributed almost evenly in the triangles determined byY.Research supported partly by the Hungarian National Foundation for Scientific Research grant No. 1812     

Self-Reciprocal Irreducible Pentanomials Over \mathbb{F}_2

Joseph Yucas and Gary Mullen conjectured that there is no self-reciprocal irreducible pentanomial of degree n over if n is divisible by 6. In this note we prove this conjecture for the case n ≡ 0, and disprove the conjecture for the case n ≡ 6 (mod 12) AMS Classifications: 11T55     

Eigenvalues of Finite Projective Planes with an Abelian Cartesian Group

Let M be an incidence matrix for a projective plane of order n. The eigenvalues of M are calculated in the Desarguesian case and a standard form for M is obtained under the hypothesis that the plane admits a (P,L)-transitivity G, |G| = n. The study of M is reduced to a principal submatrix A which is an incidence matrix for n ² lines of an associated affine plane. In this case, A is a generalized Hadamard matrix of order n for the Cayley permutation representation R(G). Under these conditions it is shown that G is a 2-group and n = 2^r when the eigenvalues of A are real. If G is abelian, the characteristic polynomial |xI – A| is the product of the n polynomials |x – (A)|, a linear character of G. This formula is used to prove n is a prime power under natural conditions on A and spectrum(A). It is conjectured that |xI – A| x ⁿ² mod p for each prime divisor p of n and the truth of the conjecture is shown to imply n = |G| is a prime power.