An algorithm for the divisors of monic polynomials over a commutative ring

Gilmer and Heinzer proved that given a reduced ring R, a polynomial f divides a monic polynomial in R[X] if and only if there exists a direct sum decomposition of R = R₀ ⊕ … ⊕ R_m (m ≤ deg f), associated to a fundamental system of idempotents e₀, … , e_m, such that the component of f in each R_i[X] has degree coefficient which is a unit of R_i. We propose to give an algorithm to explicitly find such a decomposition. Moreover, we extend this result to divisors of doubly monic Laurent polynomials.     

Graphs with Special Arcs and Cryptography

A combinatorial method of encryption with a similarity to the classical scheme of linear coding has been suggested by the author. The general idea is to treat vertices of a graph as messages and arcs of a certain length as encryption tools. We will study the quality of such an encryption in the case of graphs of high girth by comparing the probability to guess the message, (vertex) at random with the probability of breaking the key, i.e. guessing the encoding arc. In fact, the quality is good for graphs which are close to the Erdös bound, defined by the Even Cycle Theorem.In the case of parallelotopic graphs, there is a uniform way to match arcs with strings in a certain alphabet. Among parallelotopic graphs we distinguish linguistic graphs of affine type whose vertices (messages) and arcs (encoding tools) both could be naturally identified with vectors over the GF(q), and neighbors of the vertex defined by a system of linear equations. We will discuss families of linguistic and parallelotopic graphs of increasing girth as the source for assymmetric cryptographic functions and related open key algorithms.Several constructions of families of linguistic graphs of high girth with good quality, complexity and expansion coefficients will be considered. Some of those constructions have been obtained via group-theoretical and geometrical techniques.     

微分中值问题中辅助函数的构造程式

给出解决微分中值问题时，所需辅助函数的构造程式，并通过实例加以详细解释．所给程式具有一定的可操作性，可帮助学生掌握同类问题解决方案中的规律性．     

Inductive Construction of Repletion

The aim of this paper is to give a purely logical construction of repletion, i.e. the reflection of an arbitrary set to a replete one. Replete sets within constructive logic were introduced independently by M. Hyland and P. Taylor as the most restrictive but sufficiently general notion of predomain suitable for the purposes of denotational semantics à la Scott.For any set A its repletion R(A) appears as an inductively defined subset of S²(A) (A S) S which can be expressed within the internal language of a model of type theory. More explicitly, R(A) is the least subset of S²(A) containing all point filters and closed under a class of generalised limit processes. Improvements of our construction arise from several results saying that it suffices for the purpose of repletion to consider more restrictive classes of generalised limit processes.     

Constructive Matrix and Orderable Groups

We study into the relationship between constructivizations of an associative commutative ring K with unity and constructivizations of matrix groups GL _n(K) (general), SL _n(K) (special), and UT _n(K) (unitriangular) over K. It is proved that for n 3, a corresponding group is constructible iff so is K. We also look at constructivizations of ordered groups. It turns out that a torsion-free constructible Abelian group is orderly constructible. It is stated that the unitriangular matrix group UT _n(K) over an orderly constructible commutative associative ring K is itself orderly constructible. A similar statement holds also for finitely generated nilpotent groups, and countable free nilpotent groups.     

Computable Homogeneous Boolean Algebras and a Metatheorem

We consider computable homogeneous Boolean algebras. Previously, countable homogeneous Boolean algebras have been described up to isomorphism and a simple criterion has been found for the existence of a strongly constructive (decidable) isomorphic copy for such. We propose a natural criterion for the existence of a constructive (computable) isomorphic copy. For this, a new hierarchy of -computable functions and sets is introduced, which is more delicate than Feiner's. Also, a metatheorem is proved connecting computable Boolean algebras and their hyperarithmetical quotient algebras.     

Locating subsets of a normed space

Within the framework of Bishop's constructive mathematics, we give conditions under which a bounded convex subset of a uniformly smooth normed space over is located, extending results presented recently by F. Richman and H. Ishihara for subsets of a Hilbert space.

     

一类推广后的Feigenbaum函数方程的光滑解

考虑一类推广后的Feigenbaum函数方程｛g（0）=1,-1≤g（x）≤1,x∈[-1,1],h（g（x））=g（g（h（x）））其中h（x）是[-1,1]上的递减光滑奇函数且满足h（0）=0,-1〈h’（x）〈0,z∈[-1,1]．利用构造性方法讨论上述方程的光滑解的存在性及唯一性．     

The continuum as a formal space

A constructive definition of the continuum based on formal topology is given and its basic properties studied. A natural notion of Cauchy sequence is introduced and Cauchy completeness is proved. Other results include elementary proofs of the Baire and Cantor theorems. From a classical standpoint, formal reals are seen to be equivalent to the usual reals. Lastly, the relation of real numbers as a formal space to other approaches to constructive real numbers is determined. Received: 11 November 1996