computer aided intuition in abstract algebra

Two examples are given in which the computer was used to supplement intuition in abstract algebra. In the first example, the computer was used to search Cayley tables of 4 element groupoids to find those which are 5-associative but not 4-associative. (n-associative means that the product of any n elements is independent of the way the factors are grouped by parentheses.) The computer generated examples suggested the existence of n element groupoids which are (2^n?2+1)-associative but not (2^n-2)-associative, for each integer n≧4.In the second example, the computer counted the numbers g₂(m) of invertible 2×2 matrices with entries chosen from the ring Z_mof integers, for m = 2, 3, 4,…, 18. The insight gained from these results led to a proof that there are

invertible n×n matrices over Z_m.Some applications to graduate and undergraduate instruction are indicated.     

Determination of a general economic location constant by monte carlo simulation

The problem of estimating the number of markets (or plants) to serve a set of sources in a given geographical area was considered. Markets were located so as to minimize total assembly cost which was considered a linear function of the weighted Euclidean distances between sources and markets. The following predictive function C_m was proposed for estimating the minimum total assembly cost for a given number of markets: $\text{C}{}_{\mathrm{m}}\text{= C}{}_1\text{?(}\text{m?1}\text{m}\text{)}{}^{\mathrm{k}}\text{(}\text{M}\text{M ? 1}\text{)}{}^{\mathrm{k}}\text{(C}{}_1\text{? C}{}_{\mathrm{M}}\text{),m = 1, 2, 3, …, M}$ where m = number of markets being located. M = maximum number of potential market sites. C₁ = minimum assembly cost when only one market is located. C_M = minimum assembly cost when all M markets are located. k = an undetermined constant which specifies the shape of the function.The validity of the C_m function and the range of the k constant were determined by computer Monte Carlo experimentation. The constant k, to a sufficient degree of approximation and ordinary use, was found independent of the number of sources and their distribution. A general economic location co     

Monadic Thue systems

Certain infinite Thue systems over a finite alphabet are studied, in particular, systems $\text{S?∑}{}^1\text{×(∑∪{e})}$ such that for each a?∑∪{e}, the set {u| (u,a)?S} is a context-freelanguage. The syntactic structure of sets of ancestors and sets of descendants is considered, as well as that of unions of congruence classes, taken over (infinite) context-free languages or regular sets. The common descendant problem is shown to be tractable while the common ancestor problem is shown to be undecidable (even for finite systems). The word problem for confluent systems of this type is shown to be tractable. The question of whether an infinite system of this type is confluent is shown to be undecidable as is the question of whether the congruence generated by such a system has a confluent presentation.     

The complexity of a multiprocessor task assignment problem without deadlines

We construct a sequence of monotone Boolean functions h_n :{0, 1}ⁿ→{0, 1}ⁿ, such that the monotone complexity of h_n is of order $\text{n}{}^2\text{log n}$. This result includes the largest known lower bound of this kind. Previously there were an $\text{Ω(n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{)}$ bound for the Boolean matrix product, an $\text{Ω(n}{}^{\mathrm{<mtext>5</mtext><mtext>3</mtext>}}\text{)}$ bound for Boolean sums and an $\text{Ω(}\text{n}{}^2\text{log}{}^2\text{n}\text{)}$ bound by the author for the same functions h_n. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems.     

Laser-induced marine bioluminescence measurements and the potential for airborne remote sensing

Bioluminescence in cultures of the dinoflagellate Pyrocystis lunula at various temperatures were stimulated using a pulsed dye laser and Rhodamine 6G dye having an optimum lasing wavelength of $\text{586 ± 30}\text{nm}$. Following an intense “first flash” response, the flash intensity decayed in logarithmic fashion with successive laser shots. Samples pulsed to exhaustion were found to completely recover during the 12 h photophase. The total stimulable light (TSL) was calculated to be between $\text{4.5 × 10}{}^{\mathrm{?10}}$ J cell^?1 and $\text{38.5 × 10}{}^{\mathrm{?10}}$ J cell^?1. The time from stimulation to maximum light emission ($\text{t}{}_{\mathrm{m}}$) was found to vary with temperature logarithmically from approximately 11°C to 28°C. The corresponding regression equation was found to predict temperatures to within ±0.4°C. These results provide the basis for predicting the feasibility of an airborne laser transceiver for mapping the distribution of ocean bioluminescence. The potential exists for determining ocean surface/near surface temperature from measurements of the response pulse time parameters.     

Three symmetric solutions of lidstone boundary value problems for difference and partial difference equations

We consider the boundary value problem $\text{δ}{}^{\mathrm{2m}}\text{y(k-m)=f(y(k),δ}{}^2\text{y(k-1),…,δ}{}^{\mathrm{2i}}\text{y(k-1),…,δ}{}^{\mathrm{2(m-1)}}\text{y(k-(m-1)))}\text{kϵ{a+1,…,b+1},}\text{δ}{}^{\mathrm{2i}}\text{y(a+1-m)=δ}{}^{\mathrm{2i}}\text{y(b+1+m-2i)=0,}\text{0≤i≤m-1,}$ where m ≥ 1 and (−1)^m f R^m → [0, ∞) is continuous. By using Amann and Leggett-Williams' fixed-point theorems, we develop growth conditions on f so that the boundary value problem has triple positive symmetric solutions. The results obtained are then applied in the investigation of radial solutions for certain partial difference equation subject to Lidstone type conditions.     

On some bounded semiAFLs and AFLs

Goldstine [8] has conjectured that not all context-free languages are contained in $\text{F}$_∩($\text{B}$)—the smallest AFL closed under intersection and containing all bounded languages. We prove this by showing that the linear context-free language pal is not in $\text{F}$_∩($\text{B}$). Inclusion relations among various subfamilies of $\text{F}$∩($\text{B}$) as well as their closure properties are studied. It is shown that all languages defined by polynomials whose coefficients are natural numbers are in $\text{M}$_∩(prod)—the smallest intersection-closed semiAFL containing the language $\text{prod}\text{=a}{}^{\mathrm{m}}\text{b}{}^{\mathrm{n}}\text{c}{}^{\mathrm{mn}}\text{s|m,n in N}$. This implies that the corresponding full semiAFL$\text{M}\text{?}$_∩ (prod) is equal to the smallest intersection-closed full semiAFL containing all recursively enumerable bounded languages. An analogous result for all bounded languages is also obtained. Since pal is not in$\text{M}\text{?}$_∩(prod), it follows that $\text{M}\text{?}$^lin_∩(prod) is a semiAFL closed under intersection and linear-erasing homomorphism but is not closed under Kleene⁺, homomorphism, or nonerasing homomorphic replication. This solves a problem considered by Book and Greibach [2]. Finally, nonprincipality of some semiAFLs and AFLs is established. As a consequence, we solve a problem of Ginsburg [6].     

Lower bounds for polynomials with algebraic coefficients

We give a method, based on algebraic geometry, to show lower bounds for the complexity of polynomials with algebraic coefficients. Typical examples are polynomials with coefficients which are roots of unity, such as

$\text{Σ}\text{j=1}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>i</mtext>}}\text{X}{}^{\mathrm{i}}$

and

$\text{Σ}\text{j=i}\text{d}\text{e}{}^{\mathrm{<mtext>2\pi i</mtext><mtext>pi</mtext>}}\text{X}{}^{\mathrm{j}}$

where p_j is the jth prime number.We apply the method also to systems of linear equations.     

Nonsimilar boundary layers on the leeside of cones at incidence

It is known that the similarity equations for the leeward line of symmetry of a cone have no solutions for $\text{?1 < k}{}_2{}^1\text{< k < k}{}_1\text{1 < 0}$, where k is the incidence parameter of Moore, and $\text{k}{}_1{}^1\text{, k}{}_2{}^1$ depend on the external Mach number and enthalpy ratio. In this paper we present evidence that a leeside integration for such k terminates at a finite distance from the vertex in a singularity of the type analyzed by Stewartson and Simpson for entry flow in a curved pipe, and compare the theory with a representative numerical solution at $\text{k = ?}\text{1}\text{2}$. A possible interpretation of this singularity is that the boundary layers growing from the windward line of symmetry have collided, and support for this view is given by windward to leeward integrations for a range of values of k. For k such that the similarity equations have solutions, these are interpreted as limits of more general solutions.     

Kupradze's functional equation for the torsion problem of prismatic bars — Part 1

St. Venant's torsion problem for a prismatic bar is reduced to an integral equation of the Fredholm type with the help of Kupradze's method: i.e. for a given load distribution on the lateral surface of the cylinder (“actual body $\text{K}{}^{\mathrm{+}}$”) imbedded in an elastic medium (“basic body $\text{K}{}^0$”), a distribution of screw dislocations has to be determined on the lateral surface in such a manner that the external region of the infinite medium (“complementary body $\text{K}{}^{\mathrm{?}}$”) will be free of tension. The unknown function is the tangential derivative of the warping function. Part 1 demonstrates the method for a smooth boundary. In part 2 the influence of the corners on the convergence of the numerical solution of the integral equation is investigated. Prismatic bars with multiconnected cross sections as well as cross sections with corners can be treated with this method.     

Selection and sorting with limited storage

When selecting from, or sorting, a file stored on a read-only tape and the internal storage is rather limited, several passes of the input tape may be required. We study the relation between the amount of internal storage available and the number of passes required to select the Kth highest of N inputs. We show, for example, that to find the median in two passes requires at least $\text{ω(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ and at most $\text{O(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log N)}$ internal storage. For probabilistic methods, $\text{θ(N}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ internal storage is necessary and sufficient for a single pass method which finds the median with arbitrarily high probability.     

Normal forms for nonautonomous difference equations

We extend Henry Poincaré's normal form theory for autonomous difference equations χ_{k + 1} = f(χ_k) to nonautonomous difference equations χ_{k + 1} = f_k(χ_k). Poincaré's nonresonance condition $\text{α}{}_{\mathrm{j}}\text{-П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{=1α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for eigenvalues is generalized to the new nonresonance condition λ_j∪$\text{α}{}_{\mathrm{j}}\text{⊔П}{}^{\mathrm{n}}{}_{\mathrm{i=1}}\text{α}{}^{\mathrm{qi}}{}_{\mathrm{i}}\text{≠0}$ for spectral intervals.     

On nonstochastic languages and homomorphic images of stochastic languages

Using a simple method we find some nonstochastic and stochastic languages related to the Dyck sets and to the languages $\text{{wcw¦w in {a, b}}{}^1\text{}}$ and $\text{{wcw}{}^{\mathrm{R}}\text{¦w in {a, b}}{}^1\text{}}$. Using the theory of uniformly distributed sequences, we present a sufficient condition for a one-letter language to be nonstochastic. Among the applications is the result that {a^p¦p is a prime} is nonstochastic. We also study the images of stochastic and rational stochastic languages under nonerasing and arbitrary homomorphisms as well as their relations to some well-known families. Finally, we introduce a large class of bounded languages and show that it is contained in /of_∩ (DUP) = the smallest intersection-closed AFL containing $\text{DUP}\text{= {a}{}^{\mathrm{n}}\text{b}{}^{\mathrm{n}}\text{¦n in N}}$, which is a subfamily of /oK(/oL_Q = the image of the family of rational stochastic languages under nonerasing homomorphisms.     

Improving loops and vanishing variables in long transportation problems

In this paper the following two results are presented: (1)A method which determines the optimal values of certain variables during the iterative solution process. The closer the current primal feasible solution is to the optimal solution, the greater the number of variables which may be determined. (2) For each current feasible solution (X_ij) of the given m × n transportation problem A, a feasible solution ($\text{X}\text{?}{}_{\mathrm{ij}}$) of an auxiliary m × m(m ?1) transportation problem $\text{A}\text{?}$ is constructed. Problem $\text{A}\text{?}$ is shown to be equivalent to an m(m ? 1) × m(m ? 1) assignment problem with two admissible cells per column. The optimally of (X_ij) is shown to imply the optimality of ($\text{X}\text{?}{}_{\mathrm{ij}}$) and conversely. The best “improving loops” (including the improving loops used in MODI) of $\text{A}\text{?}$ are shown to be the best “improving loops” of A as well.     

Averaging shifted histograms

A method which consists in shifting different histograms of the same spectrum and then taking their average is presented in order to smooth the data and to increase the localization accuracy and separation of the peaks. The statistical properties of this method are investigated. The average of two histograms with shifted bin limits is studied. It is shown that for histograms with random bin limits, distributed according to

$\text{F}{}_{\mathrm{i}}\text{(x)=}\text{∫}\text{?∞}\text{x}\text{?}{}_{\mathrm{i}}\text{(ξ, μ}{}_{\mathrm{i}}\text{, σ)}\text{d}\text{ξ}$

; where the standard deviation σ is very small compared to the difference of the means (μ_i+1 ? μ_i) for ll i the zero order approximation to the variance of this histogram is given by:

$\text{var}\text{∽}\text{(H)=}\text{∑}\text{i=0}\text{m}\text{(A}{}_{\mathrm{i+1}}\text{?a}{}_{\mathrm{i}}\text{)}{}^2\text{F}{}_{\mathrm{i+1}}\text{(x)(1?F}{}_{\mathrm{i+1}}\text{(x))}$

, where

$\text{a}{}_{\mathrm{i}}\text{=}\text{1}\text{x}{}_{\mathrm{i=1}}\text{?x}{}_{\mathrm{i}}\text{∫}\text{x}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i+1}}\text{g(ξ)}\text{d}\text{ξ}$

and g is an unknown function fitted by the histogram. Formula (1) gives also the relation:

$\text{v}\text{a}\text{?}\text{r}\text{(}\text{(H}{}_1\text{+ H}{}_2\text{)}\text{2}\text{) =}\text{1}\text{4}\text{(}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_1\text{(x)) +}\text{v}\text{a}\text{?}\text{r}\text{(H}{}_2\text{(x))}$

, when H₁ and H₂ have stochastically independent bin limits.When the histogram H is considered as a spline function S of order one it is shown that for the minimization criterion with respect to the coefficient of the spline:

$\text{M}{}_1\text{=}\text{min}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{(g(x) ? S}{}_1\text{(x))}{}^2\text{d}\text{x}$

, the following result holds: $\text{M}{}_{\mathrm{a}}\text{?}{}^1{}_2\text{(M}{}_1\text{+ M}{}_2\text{)}$, where $\text{S}{}_{\mathrm{a}}\text{(x) =}{}^1{}_2\text{(S}{}_1\text{(x) + S}{}_2\text{(x))}$. If the number of shifted histograms tends to infinity, then

$\text{S}{}_{\mathrm{\infty }}\text{(x) = [Γ(x + h) + Γ(x ? h) ? 2Γ(x)]/h}{}^2$

, where $\text{Γ(x) =}\text{∫}\text{?∞}\text{x}\text{∫}\text{?∞}\text{η}\text{g(ξ)}\text{d}\text{ξ}\text{d}\text{η}$, and h is a constant bin size. Then

$\text{M}{}_{\mathrm{\infty }}\text{≈}\text{h}{}^4\text{144}\text{∫}\text{x}{}_1\text{x}{}_{\mathrm{m+1}}\text{g″}{}^2\text{(x)}\text{D}\text{x}$

. Extensions to two-dimensional histograms and to higher order (empirical distributions) are presented.     

A pyramid that grows by powers of 2

The features of a new pyramid scheme are presented. It is based on a decomposition of a square grid into overlapping 2 × 2 blocks. The diagonal of the square cell becomes the side of a square at the next higher level. Assume unit length at the bottom level 0 of the pyramid, then the side length of a cell at level n is $\text{2}{}^{\mathrm{<mtext>n</mtext><mtext>2</mtext>}}$. The number of the elements at level n + 1 is one half of the level n.