<Emphasis Type="Italic">P</Emphasis>≠<Emphasis Type="Italic">NP</Emphasis> for Infinite Time Turing Machines

We state different versions of the P=?NP problem for infinite time Turing machines. It is observed that PNP collapses to the fact that there are analytic sets which are not Borel.The author thanks J. D. Hamkins, R. Schipperus, and P. Welch for comments on earlier versions of this paper. He thanks Sanders Seliverstov for pointing out an inaccuracy in the first version of the proof of Theorem 2.10.Received April 19, 2002; in revised form June 10, 2002 Published online May 16, 2003     

On blocks with <Emphasis Type="Italic">K</Emphasis>(<Emphasis Type="Italic">B</Emphasis>)−<Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">B</Emphasis>)=1

We use the method of local representation and original method of Brauer to study the block with K(B)−L(B)=1, and get some properties on the defect group and the structure of this kind of blocks. Then, we show that K(B) conjecture holds for this kind of blocks.     

On Analytic Campanato and <Emphasis Type="Italic">F</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, <Emphasis Type="Italic">q</Emphasis>, <Emphasis Type="Italic">s</Emphasis>) Spaces

We investigate the relation between analytic Campanato spaces \(\mathcal {AL}_{p,s}\) and the spaces F(p, q, s), characterize the bounded and compact Riemann–Stieltjes operators from \(\mathcal {AL}_{p,s}\) to \(F(p,p-s-1,s)\). We also describe the corona theorem and the interpolating sequences for the class \(F(p,p-2,s)\), which is the Möbius invariant subspace of the analytic Besov type spaces \(B_p(s)\).     

On the equation Δ<Emphasis Type="Italic">u</Emphasis> + <Emphasis Type="Italic">q</Emphasis>(<Emphasis Type="Italic">x</Emphasis>)<Emphasis Type="Italic">u</Emphasis> = 0

Sufficient conditions for the blow-up of nontrivial generalized solutions of the interior Dirichlet problem with homogeneous boundary condition for the homogeneous elliptic-type equation Δu + q(x)u = 0, where either q(x) ≠ const or q(x) = const= λ > 0, are obtained. A priori upper bounds (Theorem 4 and Remark 6) for the exact constants in the well-known Sobolev and Steklov inequalities are established.     

New <Emphasis Type="Italic">P</Emphasis>–<Emphasis Type="Italic">Q</Emphasis> mixed modular equations and their applications

In his second notebook, Ramanujan recorded total of seven P–Q modular equations involving theta-function \(f(-q)\) with moduli of orders 1, 3, 5 and 15. In this paper, modular equations analogous to those recorded by Ramanujan are obtained for higher orders. As a consequence, several values of quotients of theta-function are evaluated. The cubic singular modulus is evaluated at \(q=\exp (-2\pi \sqrt{n/3})\) for \(n\in \{5k, 1/5k, 5/k, k/5\}\), where \(k\in \{4,7,16\}\).     

On the Crossing Number of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> □ <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K_m □ P_n), the crossing number of the Cartesian product K_m □ P_n. We prove that for m ≥ 3,n ≥ 1 and cr(K_m □ P_n)≥ (n − 1)cr(K_m+2 − e) + 2cr(K_m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K₆ □ P_n) = 15n + 3. Research supported by NFSC (60373096, 60573022).     

An <Emphasis Type="Italic">L</Emphasis>-approach for packing (<Emphasis Type="Italic">ℓ</Emphasis>, <Emphasis Type="Italic">w</Emphasis>)-rectangles into rectangular and <Emphasis Type="Italic">L</Emphasis>-shaped pieces

This paper presents an approach using a recursive algorithm for packing (?, w)-rectangles into larger rectangular and L-shaped pieces. Such a problem has actual applications for non-guillotine cutting and pallet/container loading. Our motivation for developing the L-approach is based on the fact that it can solve difficult pallet loading instances. Indeed, it is able to solve all testing problems (more than 20 000 representatives of infinite equivalence classes of the literature), including the 18 hard instances unresolved by other heuristics. We conjecture that the L-approach always finds optimum packings of (?, w)-rectangles into rectangular pieces. Moreover, the approach may also be useful when dealing with cutting and packing problems involving L-shaped pieces.     

A theorem of the alternatives for the equation |<Emphasis Type="Italic">Ax</Emphasis>| − |<Emphasis Type="Italic">B</Emphasis>||<Emphasis Type="Italic">x</Emphasis>| = <Emphasis Type="Italic">b</Emphasis>

A theorem of the alternatives for the equation \({|Ax|-|B||x|=b\ (A,B\in{\mathbb{R}}^{n\times n},\, b\in{\mathbb{R}}^n)}\) is proved and several consequences are drawn. In particular, a class of matrices A, B is identified for which the equation has exactly 2 ⁿ solutions for each positive right-hand side b.     

Systematic Construction of <Emphasis Type="Italic">q</Emphasis>-Analogs of <Emphasis Type="Italic">t</Emphasis>−(<Emphasis Type="Italic">v</Emphasis>,<Emphasis Type="Italic">k</Emphasis>,λ)-Designs

In the present paper we consider a q-analog of t–(v,k,)-designs. It is canonic since it arises by replacing sets by vector spaces over GF(q), and their orders by dimensions. These generalizations were introduced by Thomas [Geom.Dedicata vol. 63, pp. 247–253 (1996)] they are called t –(v,k,;q)- designs. A few of such q-analogs are known today, they were constructed using sophisticated geometric arguments and case-by-case methods. It is our aim now to present a general method that allows systematically to construct such designs, and to give complete catalogs (for small parameters, of course) using an implemented software package. &nbsp; In order to attack the (highly complex) construction, we prepare them for an enormous data reduction by embedding their definition into the theory of group actions on posets, so that we can derive and use a generalization of the Kramer-Mesner matrix for their definition, together with an improved version of the LLL-algorithm. By doing so we generalize the methods developed in a research project on t –(v,k,)-designs on sets, obtaining this way new results on the existence of t–(v,k,;q)-designs on spaces for further quintuples (t,v,k,;q) of parameters. We present several 2–(6,3,;2)-designs, 2–(7,3,;2)-designs and, as far as we know, the very first 3-designs over GF(q).classification 05B05     

Derivatives for smooth representations of <Emphasis Type="Italic">GL</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, ℝ) and <Emphasis Type="Italic">GL</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, ℂ)

The notion of derivatives for smooth representations of GL(n, ? _p ) was defined in [BZ77]. In the archimedean case, an analog of the highest derivative was defined for irreducible unitary representations in [Sah89] and called the “adduced” representation. In this paper we define derivatives of all orders for smooth admissible Fréchet representations of moderate growth. The real case is more problematic than the p-adic case; for example, arbitrary derivatives need not be admissible. However, the highest derivative continues being admissible, and for irreducible unitarizable representations coincides with the space of smooth vectors of the adduced representation.In the companion paper [AGS] we prove exactness of the highest derivative functor, and compute highest derivatives of all monomial representations.We apply those results to finish the computation of adduced representations for all irreducible unitary representations and to prove uniqueness of degenerate Whittaker models for unitary representations, thus completing the results of [Sah89, Sah90, SaSt90, GS13a].     

On common values of <Emphasis Type="Italic">φ</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) and <Emphasis Type="Italic">σ</Emphasis>(<Emphasis Type="Italic">m</Emphasis>). I

We show, conditional on a uniform version of the prime k-tuples conjecture, that there are x/(log x)^1+o(1) numbers not exceeding x common to the ranges of φ and σ. Here φ is Euler’s totient function and σ is the sum-of-divisors function.     

The commutation relation <Emphasis Type="Italic">xy</Emphasis>=<Emphasis Type="Italic">qyx</Emphasis>+<Emphasis Type="Italic">hf</Emphasis>(<Emphasis Type="Italic">y</Emphasis>) and Newton’s binomial formula

Let x and y be two variables satisfying the commutation relation xy=qyx+hf(y), where f(y) is a polynomial. In this paper, using Young diagrams and generating functions techniques, we study the binomial formula (x+y) ⁿ and we present an identity for x ^m y. The connection to Operator Calculus is discussed and several special cases are treated explicitly.     

On <Emphasis Type="Italic">g</Emphasis>-<Emphasis Type="Italic">α</Emphasis>-irresolute functions

We introduce the so-called g-α-irresolute functions in generalized topological spaces. We obtain some properties and several characterizations of this type of functions.     

Period of the adelic Ikeda lift for <Emphasis Type="Italic">U</Emphasis>(<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">m</Emphasis>)

We give a period formula for the adelic Ikeda lift of an elliptic modular form f for U(m, m) in terms of special values of the adjoint L-functions of f. This is an adelic version of Ikeda’s conjecture on the period of the classical Ikeda lift for U(m, m).     

Difference sets with <Emphasis Type="Italic">n</Emphasis> = 5<Emphasis Type="Italic"> p</Emphasis><Superscript><Emphasis Type="Italic">r</Emphasis></Superscript>

Let D be a (v, k, λ)-difference set in an abelian group G, and (v, 31) = 1. If n = 5p ^r with p a prime not dividing v and r a positive integer, then p is a multiplier of D. In the case 31|v, we get restrictions on the parameters of such difference sets D for which p may not be a multiplier.      

On nonregular ideals and <Emphasis Type="Italic">z</Emphasis>°-ideals in <Emphasis Type="Italic">C</Emphasis>(<Emphasis Type="Italic">X</Emphasis>)

The spaces X in which every prime z°-ideal of C(X) is either minimal or maximal are characterized. By this characterization, it turns out that for a large class of topological spaces X, such as metric spaces, basically disconnected spaces and one-point compactifications of discrete spaces, every prime z°-ideal in C(X) is either minimal or maximal. We will also answer the following questions: When is every nonregular prime ideal in C(X) a z°-ideal? When is every nonregular (prime) z-ideal in C(X) a z°-ideal? For instance, we show that every nonregular prime ideal of C(X) is a z°-ideal if and only if X is a ?-space (a space in which the boundary of any zeroset is contained in a zeroset with empty interior).     

(<Emphasis Type="Italic">K</Emphasis>, <Emphasis Type="Italic">N</Emphasis>)-Convexity and the Curvature-Dimension Condition for Negative <Emphasis Type="Italic">N</Emphasis>

We extend the range of N to negative values in the (K, N)-convexity (in the sense of Erbar–Kuwada–Sturm), the weighted Ricci curvature \(\mathop {\mathrm {Ric}}\nolimits _N\) and the curvature-dimension condition \(\mathop {\mathrm {CD}}\nolimits (K,N)\). We generalize a number of results in the case of \(N>0\) to this setting, including Bochner’s inequality, the Brunn–Minkowski inequality and the equivalence between \(\mathop {\mathrm {Ric}}\nolimits _N \ge K\) and \(\mathop {\mathrm {CD}}\nolimits (K,N)\). We also show an expansion bound for gradient flows of Lipschitz (K, N)-convex functions.     

The crossing number of <Emphasis Type="Italic">G</Emphasis> ▭ <Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> for the graph <Emphasis Type="Italic">G</Emphasis> on six vertices

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G□C _n for some graphs G on five and six vertices and the cycle C _n are also given. In this paper, we extend these results by determining the crossing number of the Cartesian product G □ C _n , where G is a specific graph on six vertices.     

Relative <Emphasis Type="Italic">t</Emphasis>-designs in binary Hamming association scheme <Emphasis Type="Italic">H</Emphasis>(<Emphasis Type="Italic">n</Emphasis>, 2)

A relative t-design in the binary Hamming association schemes H(n, 2) is equivalent to a weighted regular t-wise balanced design, i.e., certain combinatorial t-design which allows different sizes of blocks and a weight function on blocks. In this paper, we study relative t-designs in H(n, 2), putting emphasis on Fisher type inequalities and the existence of tight relative t-designs. We mostly consider relative t-designs on two shells. We prove that if the weight function is constant on each shell of a relative t-design on two shells then the subset in each shell must be a combinatorial \((t-1)\)-design. This is a generalization of the result of Kageyama who proved this under the stronger assumption that the weight function is constant on the whole block set. Using this, we define tight relative t-designs for odd t, and a strong restriction on the possible parameters of tight relative t-designs in H(n, 2). We obtain a new family of such tight relative t-designs, which were unnoticed before. We will give a list of feasible parameters of such relative 3-designs with \(n \le 100\), and then we discuss the existence and/or the non-existence of such tight relative 3-designs. We also discuss feasible parameters of tight relative 4-designs on two shells in H(n, 2) with \(n \le 50\). In this study we come up with the connection on the topics of classical design theory, such as symmetric 2-designs (in particular 2-\((4u-1,2u-1,u-1)\) Hadamard designs) and Driessen’s result on the non-existence of certain 3-designs. We believe Problems 1 and 2 presented in Sect. 5.2 open a new way to study relative t-designs in H(n, 2). We conclude our paper listing several open problems.     

On <Emphasis Type="Italic">α</Emphasis>-regular archimedean <Emphasis Type="Italic">f</Emphasis>-rings

For a commutative ring A with identity, and for infinite cardinals α as well as the symbol ∞, which indicates the situation in which there are no cardinal restrictions, one defines A to be α-regular if for each subset D of A, with |D| < α and de = 0, for any two distinct d, e ∈ D, there is an s ∈ A such that d ² s = d, for each d ∈ D, and if xd = 0, for each d ∈ D, then xs = 0