Search results for " proof"
showing 10 items of 118 documents
The complex of words and Nakaoka stability
2005
We give a new simple proof of the exactness of the complex of injective words and use it to prove Nakaoka's homology stability for symmetric groups. The methods are generalized to show acyclicity in low degrees for the complex of words in "general position". Hm(§ni1;Z) = Hm(§n;Z) for n=2 > m where §n denotes the permutation group of n elements. An elementary proof of this fact has not been available in the literature. In the first section the complex C⁄(m) of abelian groups is studied which in de- gree n is freely generated by injective words of length n. The alphabet consists of m letters. The complex C⁄(m) has the only non vanishing homology in degree m (Theorem 1). This is a result of F.…
Quasi-Modes in Higher Dimension
2019
Recall that if a(x, ξ) and b(x, ξ) are two C1-functions defined on some domain in \({\mathbf {R}}^{2n}_{x,\xi }\), then we can define the Poisson bracket to be the C0-function on the same domain given by $$\displaystyle \{ a,b\} =a^{\prime }_\xi \cdot b^{\prime }_x-a^{\prime }_x \cdot b^{\prime }_\xi =H_a(b). $$ Here \(H_a=a^{\prime }_\xi \cdot \partial _x-a^{\prime }_x\cdot \partial _\xi \) denotes the Hamilton vector field of a. The following result is due to Zworski, who obtained it via a semi-classical reduction from the above mentioned result of Hormander. A direct proof was given in Dencker et al. and here we give a variant. We will assume some familiarity with symplectic geometry.
Descriptive Complexity, Lower Bounds and Linear Time
1999
This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of lo…
The Topology of the Milnor Fibration
2020
The fibration theorem for analytic maps near a critical point published by John Milnor in 1968 is a cornerstone in singularity theory. It has opened several research fields and given rise to a vast literature. We review in this work some of the foundational results about this subject, and give proofs of several basic “folklore theorems” which either are not in the literature, or are difficult to find. Examples of these are that if two holomorphic map-germs are isomorphic, then their Milnor fibrations are equivalent, or that the Milnor number of a complex isolated hypersurface or complete intersection singularity \((X, \underline {0})\) does not depend on the choice of functions that define …
Using the Theory of Regular Functions to Formally Prove the ε-Optimality of Discretized Pursuit Learning Algorithms
2014
Learning Automata LA can be reckoned to be the founding algorithms on which the field of Reinforcement Learning has been built. Among the families of LA, Estimator Algorithms EAs are certainly the fastest, and of these, the family of Pursuit Algorithms PAs are the pioneering work. It has recently been reported that the previous proofs for e-optimality for all the reported algorithms in the family of PAs have been flawed. We applaud the researchers who discovered this flaw, and who further proceeded to rectify the proof for the Continuous Pursuit Algorithm CPA. The latter proof, though requires the learning parameter to be continuously changing, is, to the best of our knowledge, the current …
Integrated Simulation and Formal Verification of a Simple Autonomous Vehicle
2018
This paper presents a proof-of-concept application of an approach to system development based on the integration of formal verification and co-simulation. A simple autonomous vehicle has the task of reaching an assigned straight path and then follow it, and it can be controlled by varying its turning speed. The correctness of the proposed control law has been formalized and verified by interactive theorem proving with the Prototype Verification System. Concurrently, the system has been co-simulated using the Prototype Verification System and the MathWorks Simulink tool: The vehicle kinematics have been simulated in Simulink, whereas the controller has been modeled in the logic language of t…
One-Counter Verifiers for Decidable Languages
2013
Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working memory, i.e. replacing the working tape(s) with a single counter, we can define some IPS’s for each decidable language. Such verifiers are called two-way probabilistic one-counter automata (2pca’s). Then, we show that by adding a fixed-size quantum memory to a 2pca, called a two-way one-counter automaton with quantum and classical states (2qcca), the protocol can be spac…
La demostración matemática: problemática actual
2002
RESUMENAnalizamos la problemática actual en torno a la demostración matemática, con particular énfasis en las ideas introducidas por las demostraciones asistidas por ordenador y por la llamada matemática experimental. Examinamos además la influencia que pueden tener estas ideas sobre el concepto de demostración y proponemos una caracterización atendiendo a las diferentes funciones que puede desempeñar la demostración en su vertientes explicativa, comunicativa, sistematizadora, como incrementadora de la comprensión de resultados y como transmisora de conocimiento y convicción. Finalmente, se ofrecen algunas conclusiones sobre problemas relacionados con la intuición, la lógica, la certeza, el…
An elementary proof of Hilbertʼs theorem on ternary quartics
2012
Abstract In 1888, Hilbert proved that every nonnegative quartic form f = f ( x , y , z ) with real coefficients is a sum of three squares of quadratic forms. His proof was ahead of its time and used advanced methods from topology and algebraic geometry. Up to now, no elementary proof is known. Here we present a completely new approach. Although our proof is not easy, it uses only elementary techniques. As a by-product, it gives information on the number of representations f = p 1 2 + p 2 2 + p 3 2 of f up to orthogonal equivalence. We show that this number is 8 for generically chosen f, and that it is 4 when f is chosen generically with a real zero. Although these facts were known, there wa…
On the Existence of 1-Bounded Bi-ideals with the WELLDOC Property
2015
A combinatorial condition called well distributedoccurrences, or WELLDOC for short, has been introducedrecently. The proofs that WELLDOC property holds for thefamily of Sturmian words, and more generally, for Arnoux-Rauzy words are given in two papers by Balkova et al. The WELLDOC property for bounded bi-ideals is analysed inthis paper. The existence of a 1-bounded bi-ideal over thefinite alphabet that satisfies the WELLDOC property has beenproved by the authors.