B. S. Tsirelson showed that comparisons between probabilities in “classical” physics and probabilities in quantum mechanics yield discrepancy measures $K_n $ for finite $n \times n$ real matrices that approach Grothendieck’s constant $K_G $ as n gets large. It is known that $K_2 = K_3 = \sqrt{2} $ and that $K_G \geq \pi /2 = 1.57 \cdots $, but examples of $n \times n$ matrices for specified n that demonstrate $K_n > \sqrt{2} $ have eluded researchers. A series of elementary examples are provided, which yield lower bounds on $K_{k ( k - 1 )} $ that approach 3/2 as k gets large. A uniform change along the main diagonal of our basic example shows that $K_{20} \geqq = 10/7 = 1.42 \cdots $.

Abstract The original UNIX system was designed to be small and intelligible, achieving power by generality rather than by a profusion of features. In this spirit we have designed and implemented IX, a multilevel‐secure variant of the Bell Labs research system. IX aims at sound, practical security, suitable for private‐and public‐sector uses other than critical national‐security applications. The major security features are: private paths for safe cooperation among privileged processes, structured management of privilege, and security labels to classify information for purposes of privacy and integrity. The labels of flies and processes are checked at every system call that involves data flow and are adjusted dynamically to assure that labels on outputs reflect labels on inputs.

Let a sequence of k-dimensional vectors ${\bf x}_0 ,{\bf x}_1 , \cdots $ (over a ring A) be determined by a polynomial recurrence of form ${\bf x}_n = T({\bf x}_{n - 1} )$, where $T:A^k \to A^k $ itself is known to be a polynomial map in k variables of degree at most d but is otherwise unknown. We show that there is a finite N such that the entire sequence $\{ {\bf x}_n :n \geqq 0\} $ can be deduced from the first $N + 1$ terms ${\bf x}_0 ,{\bf x}_1 , \cdots ,{\bf x}_N $ alone. The number $N = \phi (d,k,A)$ depends on d and k and the ring A but not on T. Let $\phi ^ * (d,k)$ denote the maximum of $\phi (d,k,A)$ over all commutative rings with unit. Then we show that $\phi ^ * (d,k) < \infty $. In particular, $\phi ^ * (d,1) = d + 1$ and $\phi ^ * (1,k) = k + 1$. In the general case $\phi ^ * (d,k) \geqq \left( {\begin{array}{*{20}c} {k + d} \\ k \\ \end{array} } \right)$ and equality does not always hold because $\phi ^ * (2,2) \geqq 7$. In addition, we show that for each k that $\max \{ \phi (d,k,{\bf F}):{\bf F}{\text{ a field}}\} $ is bounded by a polynomial in d. These results are applied to the problem of correctly extrapolating the values $\{ {{\bf x}_i :i \geqq 0} \}$ of an unknown polynomial recurrence $(\bmod M)$ in k variables of degree at most d, where d and k are known and M is not known. A polynomial-time algorithm is given which computes a value $\hat {\bf x}_{n + 1} $ given the values $\{ {{\bf x}_i :0 \leqq i \leqq n} \}$ of such a recurrence as input, and it is shown that $\hat {\bf x}_{n + 1} \ne {\bf x}_{n + 1} $ for at most \[ 1 + \phi ^ * (d,k) + \log \left( {M^{dN} N^{\tfrac{1}{2}N} } \right) \] values of n, where $N = 1 + k\left( {\begin{array}{*{20}c} {k + d} \\ k \\ \end{array} } \right)$.

A random loop, or polygon, is a simple random walk whose trajectory is a simple Jordan curve. The study of random loops is extended in two ways. First, the probability P/sub n/(x,y) that a random n-step loop contains a point (x,y) in the interior of the loop is studied, and (1/2, 1/2) is shown to be (1/2)-(1/n). It is plausible that P/sub n/(x,y) tends toward 1/2 for all (x,y), but this is not proved even for (x,y)=(3/2,1/2) A way is offered to simulate random n-step self-avoiding loops. Numerical evidence obtained with this simulation procedure suggests that the probability P/sub n/(3/2,1/2) approximately=(1/2)-(c/n), for some fixed c.>

The Berlekamp–Massey algorithm takes a sequence of elements from a field and finds the shortest linear recurrence (or linear feedback shift register) that can generate the sequence. In this paper we extend the algorithm to the case when the elements of the sequence are integers modulo m, where m is an arbitrary integer with known prime decomposition.

A general cryptanalysis method is presented based on statistical estimation theory. It is applied to two systems of practical interest: rotor machines and substitution-permutation networks. To cryptanalyze these systems, the finite keyspace is imbedded in a continuous set and the key estimate is a proper quantization of the continuous maximum likelihood estimate. Promising cryptanalysis results of a rotor machine under a ciphertext only attack and a substitution-permutation network under a known plaintext attack are presented.