On packing squares with equal squares

The following problem arises in connection with certain multidimensional stock cutting problems:How many nonoverlapping open unit squares may be packed into a large square of side α?Of course, if α is a positive integer, it is trivial to see that α² unit squares can be succesfully packed. However, if α is not an integer, the problem becomes much more complicated. Intuitively, one feels that for $\text{α = N + (}\text{1}\text{100}\text{)}$, say (where N is an integer), one should pack N² unit squares in the obvious way and surrender the uncovered border area (which is about $\text{α}\text{50}$) as unusable waste. After all, how could it help to place the unit squares at all sorts of various skew angles?In this note, we show how it helps. In particular, we prove that we can always keep the amount of uncovered area down to at most proportional to $\text{α}{}^{\mathrm{<mtext>7</mtext><mtext>11</mtext>}}$, which for large α is much less than the linear waste produced by the “natural” packing above.     

Evaluating polynomials over the unit disk and the unit ball

We investigate the use of orthonormal polynomials over the unit disk ??² in ?² and the unit ball ??³ in ?³. An efficient evaluation of an orthonormal polynomial basis is given, and it is used in evaluating general polynomials over ??² and ??³. The least squares approximation of a function f on the unit disk by polynomials of a given degree is investigated, including how to write a polynomial using the orthonormal basis. Matlab codes are given.     

Covering tori with squares

We find that an n × n toroidal checkerboard can be covered with $\text{?}\text{n}\text{k}\text{?}\text{n}\text{k}\text{??}$k × k squares, and no fewer. To prove this result we also need to prove that the unit Euclidean torus can be covered with ?α^?1?α^?1?? squares of side α, and no fewer.     

Packing equal squares into a large square

Let s(x) denote the maximum number of non-overlapping unit squares which can be packed into a large square of side length x. Let W(x)=x²−s(x) denote the “wasted” area, i.e., the area not covered by the unit squares. In this note we prove that

     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

Piecewise linear least squares approximations of Frobenius-Perron operators

We propose a piecewise linear numerical method based on least squares approximations for computing stationary density functions of Frobenius-Perron operators associated with piecewise C² and stretching mappings of the unit interval. We prove the weak convergence of the method for a class of Frobenius-Perron operators, and the numerical results show that it is also norm convergent and has a better convergence rate than the piecewise linear Markov approximation method.     

The crystal and molecular structure of 3, 4-dihydroxy L-phenyl-alanine

The molecule crystallizes in spacegroup P2₁ with two molecules per unit cell. The unit cell dimensions area = 6.044 Å,b = 13.607 Å,c = 5.311 Å,γ = 97.55°. The density was calculated to be 1.512 g.ml.^?1 and found to be 1.51 g.ml.^?1 The major atoms were located by the reliable image method and the hydrogen atoms were located from a difference electron density map. Full-matrix least squares refinement of the parameters yielded an unweighted residual indexR of 0.088. The bond lengths and angles of the amino acid grouping are consistent with values in other amino acids. The structural parameters of the aromatic system are very similar to those of noradrenaline and dopamine hydrochlorides. The crystal structure is dominated by a three-dimensional intermolecular hydrogen bonding system. The molecular conformation is different from that displayed by any other aromatic amino acid or peptide whose crystal structure is known.     

Magic square spectra

To study the eigenvalues of low order singular and non-singular magic squares we begin with some aspects of general square matrices. Additional properties follow for general semimagic squares (same row and column sums), with further properties for general magic squares (semimagic with same diagonal sums). Parameterizations of general magic squares for low orders are examined, including factorization of the linesum eigenvalue from the characteristic polynomial.For nth order natural magic squares with matrix elements 1,…,n² we find examples of some remarkably singular cases. All cases of the regular (or associative, or symmetric) type (antipodal pair sum of 1+n²) with n-1 zero eigenvalues have been found in the only complete sets of these squares (in fourth and fifth order). Both the Jordan form and singular value decomposition (SVD) have been useful in this study which examines examples up to 8th order.In fourth order these give examples illustrating a theorem by Mattingly that even order regular magic squares have a zero eigenvalue with odd algebraic multiplicity, m. We find 8 cases with m=3 which have a non-diagonal Jordan form. The regular group of 48 squares is completed by 40 squares with m=1, which are diagonable. A surprise finding is that the eigenvalues of 16 fourth order pandiagonal magic squares alternate between m=1, diagonable, and m=3, non-diagonable, on rotation by π/2. Two 8th order natural magic squares, one regular and the other pandiagonal, are also examined, found to have m=5, and to be diagonable.Mattingly also proved that odd order regular magic squares have a zero eigenvalue with even multiplicity, m=0,2,4,... Analyzing results for natural fifth order magic squares from exact backtracking calculations we find 652 with m=2, and four with m=4. There are also 20, 604 singular seventh order natural ultramagic (simultaneously regular and pandiagonal) squares with m=2, demonstrating that the co-existence of regularity and pandiagonality permits singularity. The singular odd order examples studied are all non-diagonable.     

Some results on construction of orthogonal Latin squares by the method of sum composition

A method of sum composition for construction of orthogona Latin squares was introduced by A. Hedayat and E. Seiden [1]. In this paper we exhibit procedures for constructing a pair of orthogonal Latin squares of size p^α + 4 for primes of the form 4m + 1 or p ≡ 1, 2, 4 mod 7. We also show that for any p > 2n and n even one can construct and orthogonal pair of Latin squares of size p^α + n using the method of sum composition. We observe that the restriction xy = 1 used by Hedayat and Seiden is sometimes necessary.     

Preconditioned conjugate gradient method for generalized least squares problems

A variant of the preconditioned conjugate gradient method to solve generalized least squares problems is presented. If the problem is min (Ax − b)^TW⁻¹(Ax − b) with A ∈ R^m×n and W ∈ R^m×m symmetric and positive definite, the method needs only a preconditioner A₁ ∈ R^n×n, but not the inverse of matrix W or of any of its submatrices. Freund's comparison result for regular least squares problems is extended to generalized least squares problems. An error bound is also given.     

A new proof of the three squares theorem

A theorem of Fein, Gordon, and Smith on the representation of ?1 as a sum of two squares is shown to yield a new proof of the three squares theorem. A positive integer k can be represented as a sum of three integer squares if and only if k ≠ 4^an with n ≡ 7 (mod 8) and a ≥ 0. This proof depends of the Brauer group and class field theory, not on ternary quadratic forms.     

Generalized Latin squares of order n with n 2 − 1 distinct elements

Let n ≥ 3 be a positive integer. We show that the number of equivalence classes of generalized Latin squares of order n with n ² ? 1 distinct elements is 4 if n = 3 and 5 if n ≥ 4. It is also shown that all these squares are embeddable in groups. As an application, we obtain a lower bound for the number of isomorphism classes of certain Eulerian graphs with n ² + 2n ? 1 vertices.     

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.     

Sumsets being squares

Alon, Angel, Benjamini and Lubetzky [1] recently studied an old problem of Euler on sumsets for which all elements of A+B are integer squares. Improving their result we prove: 1. There exists a set A of 3 positive integers and a corresponding set B?[0,N] with |B|?(logN)^15/17, such that all elements of A+B are perfect squares. 2. There exists a set A of 3 integers and a corresponding set B?[0,N] with |B|?(logN)^9/11, such that all elements of the sets A, B and A+B are perfect squares. The proofs make use of suitably constructed elliptic curves of high rank.     

The square of a block graph

The square H² of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. A block graph is one in which every block is a clique. For the first time, good characterizations and a linear time recognition of squares of block graphs are given in this paper. Our results generalize several previous known results on squares of trees.     

Contractible Exact Squares

Exact squares in Cat are not necessarily absolute (i.e., preserved by any 2-functor Cat → Cat), or even preserved by any 2-functor given by exponentiation (?)^? : Cat → Cat: if a square is preserved by exponentiation it will be called a contractible exact square. We will characterize diagrammatically these contractible squares, and among them the contractible categories, and the so called fibering and cofibering squares, with especially the comma squares and the adjunction squares. As an application we conclude with a diagrammatical characterization of absolutely absolute Kan extensions and especially of absolutely final functors and of absolutely absolute colimits.     

The polynomial Fourier transform with minimum mean square error for noisy data

In 2006, Naoki Saito proposed a Polyharmonic Local Fourier Transform (PHLFT) to decompose a signal f∈L²(Ω) into the sum of a polyharmonic componentu and a residualv, where Ω is a bounded and open domain in R^d. The solution presented in PHLFT in general does not have an error with minimal energy. In resolving this issue, we propose the least squares approximant to a given signal in L²([−1,1]) using the combination of a set of algebraic polynomials and a set of trigonometric polynomials. The maximum degree of the algebraic polynomials is chosen to be small and fixed. We show in this paper that the least squares approximant converges uniformly for a Hölder continuous function. Therefore Gibbs phenomenon will not occur around the boundary for such a function. We also show that the PHLFT converges uniformly and is a near least squares approximation in the sense that it is arbitrarily close to the least squares approximant in L² norm as the dimension of the approximation space increases. Our experiments show that the proposed method is robust in approximating a highly oscillating signal. Even when the signal is corrupted by noise, the method is still robust. The experiments also reveal that an optimum degree of the trigonometric polynomial is needed in order to attain the minimal l² error of the approximation when there is noise present in the data set. This optimum degree is shown to be determined by the intrinsic frequency of the signal. We also discuss the energy compaction of the solution vector and give an explanation to it.     

Nonnegative functions as squares or sums of squares

We prove that, for n?4, there are C^∞ nonnegative functions f of n variables (and even flat ones for n?5) which are not a finite sum of squares of C² functions. For n=1, where a decomposition in a sum of two squares is always possible, we investigate the possibility of writing f=g². We prove that, in general, one cannot require a better regularity than g∈C¹. Assuming that f vanishes at all its local minima, we prove that it is possible to get g∈C² but that one cannot require any additional regularity.     

Regularity of subelliptic Monge-Ampère equations

In dimension n?3, for k≈|x|^2m that can be written as a sum of squares of smooth functions, we prove that a C² convex solution u to a subelliptic Monge-Ampère equation detD²u=k(x,u,Du) is itself smooth if the elementary (n−1)st symmetric curvature kn−1 of u is positive (the case m?2 uses an additional nondegeneracy condition on the sum of squares). Our proof uses the partial Legendre transform, Calabi's identity for ∑uijσij where σ is the square of the third order derivatives of u, the Campanato method Xu and Zuily use to obtain regularity for systems of sums of squares of Hörmander vector fields, and our earlier work using Guan's subelliptic methods.     

Quantitative relation between noise sensitivity and influences

A Boolean function f: {0,1} ⁿ → {0,1} is said to be noise sensitive if inserting a small random error in its argument makes the value of the function almost unpredictable. Benjamini, Kalai and Schramm [3] showed that if the sum of squares of inuences of f is close to zero then f must be noise sensitive. We show a quantitative version of this result which does not depend on n, and prove that it is tight for certain parameters. Our results hold also for a general product measure µ _p on the discrete cube, as long as log1/p?logn. We note that in [3], a quantitative relation between the sum of squares of the inuences and the noise sensitivity was also shown, but only when the sum of squares is bounded by n ^?c for a constant c. Our results require a generalization of a lemma of Talagrand on the Fourier coefficients of monotone Boolean functions. In order to achieve it, we present a considerably shorter proof of Talagrand’s lemma, which easily generalizes in various directions, including non-monotone functions.