Mathematics Commons^™

Sensible Rules For Remembering Duals -- The S-O-B Method, Arthur T. Benjamin

All HMC Faculty Publications and Research

We present a natural motivation and simple mnemonic for creating the dual LP of any linear programing problem.

Analysis Of A Recurrence Arising From A Construction For Nonblocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers n > 1 by the recurrence f(n) = min( n, min_m|n( 2f(m) + 3f(n/m) ). The function f has f(n) = n as its upper envelope, attained for all prime n.

The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form f(n) ~ C(log n)^{1 + 1/γ} for certain constants γ and C, in the sense that for any ε > 0, the inequality f(n) ≤ (C + ε)(log n)^{1 + 1/γ} holds for infinitely many n, while f(n) ≤ (C + ε)(log …

Analysis Of A Recurrence Arising From A Construction For Non-Blocking Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

Define f on the integers $n > 1$ by the recurrence $f( n ) = \min \{ n,\min _{m|n} 2f( m ) + 3f( n/m ) \}$. The function f has $f( n ) = n$ as its upper envelope, attained for all prime n. The goal of this paper is to determine the corresponding lower envelope. It is shown that this has the form $f( n ) \sim C( \log n )^{1 + 1/\gamma } $ for certain constants $\gamma $ and C, in the sense that for any $\varepsilon > 0$, the inequality $f( n ) \leq ( …

Optimal Klappenspiel, Arthur T. Benjamin, Derek Stanford '93

All HMC Faculty Publications and Research

The game Klappenspiel ("flipping game") is a traditional German game of flipping tiles according to dice rolls. In this paper, we derive the optimal strategy for this game by using dynamic programming. We show that the probability of winning using the optimal strategy is 0.30%.

Multiple Solutions For A Semilinear Dirichlet Problem, Alfonso Castro, Jorge Cossio

All HMC Faculty Publications and Research

The authors prove that a semilinear elliptic boundary value problem has five solutions when the range of the derivative of the nonlinearity includes at least the first two eigenvalues. Extensive use is made of Lyapunov–Schmidt reduction arguments, the mountain pass lemma, and characterizations of the local degree of critical points.

Multiple Solutions For A Nonlinear Dirichlet Problem, Alfonso Castro, Jorge Cossio

All HMC Faculty Publications and Research

The authors prove that a semilinear elliptic boundary value problem has five solutions when the range of the derivative of the nonlinearity includes at least the first two eigenvalues. Extensive use is made of Lyapunov-Schmidt reduction arguments, the mountain pass lemma, and characterizations of the local degree of critical points.

Lattice-Ordered Algebras That Are Subdirect Products Of Valuation Domains, Melvin Henriksen, Suzanne Larson, Jorge Martinez, R. G. Woods

All HMC Faculty Publications and Research

An f-ring (i.e., a lattice-ordered ring that is a subdirect product of totally ordered rings) A is called an SV-ring if A/P is a valuation domain for every prime ideal P of A. If M is a maximal ℓ-ideal of A , then the rank of A at M is the number of minimal prime ideals of A contained in M, rank of A is the sup of the ranks of A at each of its maximal ℓ-ideals. If the latter is a positive integer, then A is said to have finite rank, and if A …

Radially Symmetric Solutions To A Dirichlet Problem Involving Critical Exponents, Alfonso Castro, Alexandra Kurepa

All HMC Faculty Publications and Research

In this paper we answer, for N = 3,4, the question raised in [1] on the number of radially symmetric solutions to the boundary value problem -Δu(x) = λu(x) + u(x)|u(x)|^{4/(N-2)}, x ε B: = x ε R^N:{|x| < 1}, u(x)=0, x ε ∂B, where Δ is the Laplacean operator and λ>0. Indeed, we prove that if N = 3,4, then for any λ>0 this problem has only finitely many radial solutions. For N = 3,4,5 we show that, for each λ>0, the set of radially symmetric solutions is bounded. Moreover, we establish geometric properties of the branches of solutions bifurcating from zero and from infinity.

Uniqueness Of Stable And Unstable Positive Solutions For Semipositone Problems, Alfonso Castro, Sudhasree Gadam

All HMC Faculty Publications and Research

Abstract not included in this article.

Review: J.M. Aarts And T. Nishiura, Dimension And Extensions (Amsterdam, London, New York, And Tokyo, 1993), Melvin Henriksen

All HMC Faculty Publications and Research

Reviewed work: J. M. Aarts and T. Nishiura. Dimension and extensions. North-Holland Math. Library, Amsterdam, London, New York, and Tokyo, 1993, xii + 331 pp., $106.50. ISBN 0444897402.

Fault-Tolerant Circuit-Switching Networks, Nicholas Pippenger, Geng Lin

All HMC Faculty Publications and Research

The authors consider fault-tolerant circuit-switching networks under a random switch failure model. Three circuit-switching networks of theoretical importance—nonblocking networks, rearrangeable networks, and superconcentrators—are studied. The authors prove lower bounds for the size (the number of switches) and depth (the largest number of switches on a communication path) of such fault-tolerant networks and explicitly construct such networks with optimal size Θ( n (log n)² ) and depth Θ( log n ).

Advection Of A Passive Scalar By A Vortex Couple In The Small-Diffusion Limit, Joseph F. Lingevitch, Andrew J. Bernoff

All HMC Faculty Publications and Research

We study the advection of a passive scalar by a vortex couple in the small-diffusion (i.e. large Péclet number, Pe) limit. The presence of weak diffusion enhances mixing within the couple and allows the gradual escape of the scalar from the couple into the surrounding flow. An averaging technique is applied to obtain an averaged diffusion equation for the concentration inside the dipole which agrees with earlier results of Rhines & Young for large times. At the outer edge of the dipole, a diffusive boundary layer of width O(Pe^−½) forms; asymptotic matching to the interior …

Finite Amplitude Convection Between Stress-Free Boundaries; Ginzburg-Landau Equations And Modulation Theory, Andrew J. Bernoff

All HMC Faculty Publications and Research

The stability theory for rolls in stress-free convection at finite Prandtl number is affected by coupling with low wavenumber two-dimensional mean-flow modes. In this work, a set of modified Ginzburg-Landau equations describing the onset of convection is derived which accounts for these additional modes. These equations can be used to extend the modulation equations of Zippelius & Siggia describing the breakup of rolls, bringing their stability theory into agreement with the results of Busse & Bolton.

The Lazer Mckenna Conjecture For Radial Solutions In The Rn Ball, Alfonso Castro, Sudhasree Gadam

All HMC Faculty Publications and Research

When the range of the derivative of the nonlinearity contains the first k eigenvalues of the linear part and a certain parameter is large, we establish the existence of 2k radial solutions to a semilinear boundary value problem. This proves the Lazer McKenna conjecture for radial solutions. Our results supplement those in [5], where the existence of k + 1 solutions was proven.

Uniqueness And Stability Of Nonnegative Solutions For Semipositone Problems In A Ball, Ismael Ali, Alfonso Castro, Ratnasingham Shivaji

All HMC Faculty Publications and Research

We study the uniqueness and stability of nonnegative solutions for classes of nonlinear elliptic Dirichlet problems on a ball, when the nonlinearity is monotone, negative at the origin, and either concave or convex.

Optimal Leapfrogging, Joel Auslander, Arthur T. Benjamin, Daniel S. Wilkerson

All HMC Faculty Publications and Research

No abstract provided in this article.

Topologies And Cotopologies Generated By Sets Of Functions, Alan Dow, Melvin Henriksen, Ralph Kopperman, R. G. Woods

All HMC Faculty Publications and Research

Let L be either [0, 1] or {0, 1} with the usual order. We study topologies on a set X for which the cozero-sets of certain subfamilies H of L^x form a base, and the properties imposed on such topologies by hypothesizing various order-theoretic conditions on H. We thereby obtain useful generalizations of extremely disconnected spaces, basically disconnected spaces, and F-spaces. In particular we use these tools to study the space of minimal prime ideals of certain commutative rings.

A Bifurcation Theorem And Applications, Alfonso Castro, Jorge Cossio

All HMC Faculty Publications and Research

In this paper we give a sufficient condition on the nonlinear operator N for a point (λ, u) to be a local bifurcation point of equations of the form u + λL^-1(N(u)) = 0, where L is a linear operator in a real Hilbert space, L has compact inverse, and λ ∈ R is a parameter. Our result does not depend on the variational structure of the equation or the multiplicity of the eigenvalue of the linear operator L. Applications are made to systems of differential equations and to the existence of periodic solutions of nonlinear second order …

An Elementary Approach To Some Analytic Asymptotics, Nicholas Pippenger

All HMC Faculty Publications and Research

Fredman and Knuth have treated certain recurrences, such as $M(0) = 1$ and\[M(n + 1) = \mathop {\min }\limits_{0 \leqslant k \leqslant n} (\alpha M(k) + \beta M(n - k)),\] where $\min (\alpha ,\beta ) > 1$, by means of auxiliary recurrences such as \[h(x) = \left\{ {\begin{array}{*{20}c} {0\qquad {\text{if}}0 \leqslant x < 1,} \\ {1 + h({x / \alpha }) + h({x / \beta }){\text{ if}}1 \leq x < \infty .} \\ \end{array} } \right.\] The asymptotic behavior of $h(x)$ as $x \to \infty $ with $\alpha $ and $\beta $ fixed depends on whether ${{\log \alpha } / {\log \alpha }}$ is rational or irrational.

The solution of Fredman and Knuth used analytic methods in both cases, and used in particular the Wiener–Ikehara Tauberian theorem in the irrational case. The author shows that a more explicit solution to these recurrences can be obtained by entirely elementary methods, based on a geometric interpretation of $h(x)$ …

What They Didn’T Tell Me About Calculus And The Computer, Melvin Henriksen

All HMC Faculty Publications and Research

My first attempt at using computers as an aid to teaching calculus began in 1966 and culminated with the publication in 1971 of Single Variahle Calculus, written jointly with Milton Lees. Everyone used a mainframe and punched cards and few knew how to program. Computer use was limited to supplementary exercises that could be done today with a hand-held programmable calculator. A constructive sequential approach to limits and elementary numerical analysis were emphasized. The absence of programming displeased computer scientists, but it was too avant garde for all but a tiny minority of teachers of calculus. Attempts by others …

Another Way Of Counting Nᴺ, Arthur T. Benjamin, Fritz Juhnke

All HMC Faculty Publications and Research

An original combinatorial proof of a combinatorial identity is presented.

Optimization In Chemical Kinetics, Arthur T. Benjamin, Gordon J. Hogenson '92

All HMC Faculty Publications and Research

No abstract provided in this article.

On A Lower Bound For The Redundancy Of Reliable Networks With Noisy Gates, Nicholas Pippenger

All HMC Faculty Publications and Research

A proof is provided that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a network with noisy gates. This result was first stated by R.L. Dobrushin and S.I. Ortyukov (1977). However, the authors believe that the analysis given by Dobrushin and Ortyukov is not entirely correct. The authors establish the result by following the same steps and by replacing the questionable part of their analysis with entirely new arguments.

Selection Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

An upper bound asymptotic to $2n\log _e n$ is established for the number of comparators required in a network that classifies $n$ values into two classes, each containing $n / 2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n / 2)\log _2 n$.)

Stochastic Orderings Induced By Star-Shaped Functions, Henry A. Krieger

All HMC Faculty Publications and Research

The non-decreasing functions whicl are star-shaped and supported above at each point of a non-empty closed proper subset of the real line induce an ordering, on the class of distribution functions with finite first moments, that is strictly weaker than first degree stochastic dominance and strictly stronger than second degree stochastic dominance. Several characterizations of this ordering are developed, both joint distribution criteria and those involving only marginals. The latter are deduced from a decomposition theorem, which reduces the problem to consideration of certain functions which are star-shaped on the complement of an open interval.

When Is Every Order Ideal A Ring Ideal?, Melvin Henriksen, Suzanne Larson, Frank A. Smith

All HMC Faculty Publications and Research

A lattice-ordered ring ℝ is called an OIRI-ring if each of its order ideals is a ring ideal. Generalizing earlier work of Basly and Triki, OIRI-rings are characterized as those f-rings ℝ such that ℝ/I is contained in an f-ring with an identity element that is a strong order unit for some nil l-ideal I of ℝ. In particular, if P(ℝ) denotes the set of nilpotent elements of the f-ring ℝ, then ℝ is an OIRI-ring if and only if ℝ/P(ℝ) is contained in an f-ring with an identity element that is a strong order unit.

The Expected Capacity Of Concentrators, Nicholas Pippenger

All HMC Faculty Publications and Research

The expected capacity of a class of sparse concentrators called modular concentrators is determined. In these concentrators, each input is connected to exactly two outputs, each output is connected to exactly three inputs, and the girth (the length of the shortest cycle in the connexion graph) is large. Two definitions of expected capacity are considered. For the first (which is due to Masson and Morris), it is assumed that a batch of customers arrive at a random set of inputs and that a maximum matching of these customers to servers at the outputs is found. The number of unsatisfied requests …

Modulated, Frequency-Locked, And Chaotic Cross-Waves, William B. Underhill, Seth Lichter, Andrew J. Bernoff

All HMC Faculty Publications and Research

Measurements were made of the wave height of periodic, quasi-periodic, and chaotic parametrically forced cross-waves in a long rectangular channel. In general, three frequencies (and their harmonics) may be observed: the subharmonic frequency and two slow temporal modulations — a one-mode instability associated with streamwise variation and a sloshing motion associated with spanwise variation. Their interaction, as forcing frequency, f, and forcing amplitude, a, were varied, produced a pattern of Arnold tongues in which two or three frequencies were locked. The overall picture of frequency-locked and -unlocked regions is explained in terms of the Arnold tongues predicted by …

Graphs, Maneuvers, And Turnpikes, Arthur T. Benjamin

All HMC Faculty Publications and Research

We address the problem of moving a collection of objects from one subset of Z^m to another at minimum cost. We show that underfairly natural rules for movement assumptions, if the origin and destination are far enough apart, then a near optimal solution with special structure exists: Our trajectory from the originto the destination accrues almost all of its cost repeatingat most m different patterns of movement. Directions for related research are identified.

Ordered Ultraconnected Rings, Melvin Henriksen, Frank A. Smith

All HMC Faculty Publications and Research

A ring R with identity element 1 is called ultraconnected if for each unital homomorphism ϕ of Z^ω into R, there is an i < ω such that ϕ(f) = f(i) • 1 for every f € Z^ω . Our main result is that if no sum of nonzero squares in R is 0 and R has only trivial idempotents, then R fails to be ultraconnected iff R contains a subring isomorphic to Z^ω/P for some free minimal prime ideal P of Z^ω.