mm-2539 === Subject: Re: Minimising near diagonal terms in a matrix Originator: israel@math.ubc.ca (Robert Israel) > Here is a pb I'd like to submit, which I guess is close to the Metric > TSP and wonder whether some of you may know a solution (exact or approx). > Given an interdistance matrix (Aij=d(Xi,Xj) for some Xi's), what is > the best permutation so that given r>0 the sum, for every line of the > matrix, of the r terms around the diagonal is minimum? Could you be a bit more explicit about what the problem is? What are you permuting? What are you minimizing? One possibility that comes to mind: Find P, a permutation of 0..N-1 to minimize N-1 (i+r)%N SUM SUM A[P[i],P[j]] i=0 j=i+1 For r=1, this is a TSP. For r> 1, I don't know how to characterize it, but if d satisfies the triangle inequality, I would expect the above TSP to be a decent approximation. Improvement algorithms of the type applied to TSPs should also work. As noted by another poster, removing the modular arithmetic would change things. === Subject: interesting family of polynomials and problem Epigone-thread: zercroiryr Originator: israel@math.ubc.ca (Robert Israel) Let Z be a positive integer. Let M = Z/2 if Z is even and (Z+1)/2 if Z is odd. For each integer k, 1<= k <= M+1 let Z = kq(k) + r(k), where q(k) and r(k) are integers and 0<=r(k) < k. Let p be a real number , 0 < p < 1. Define V(k,p) = (k-r(k))q(k)p^q(k) + r(k)(q(k)+1)p^(q(k)+1). whenever 1<=k<= M+1. Define f_k(p) = V(k,p) - V(k-1,p), for 2<= k <= M+1 so f_k(p) is a polynomial in p. The polynomials f_k(p) have some interesting properties: 1. Whenever j > k , f'_j(1) >= f'_k(1), with equality iff f_j = f_k. 2. if f_i != f_j, then there is unique p(i,j) in (0,1) such that f_i(p(i,j)) = f_j(p(i,j)), and moreover p(i,j) is a simple root of f_i - f_j. 3. if j > i and 0 < p < 1 then f_j(p) = f_i(p) > 0 if and only if 0 < p < p(i,j). these 3 properties are not difficult to show. can one show the following? 4. if p(i,j) and p(i,k) are defined, and k > j, then p(i,k) <= p(i,j) . Are there other families of polynomials that have this decreasing roots property? tom foregger === Subject: Journal of Knot Theory and Its Ramifications - Table of Contents Alert Originator: israel@math.ubc.ca (Robert Israel) Vol. 12, No. 5 of Journal of Knot Theory and Its Ramifications (JKTR) is out. Articles are available in electronic format from http://www.worldscinet.com/jktr.html Table-of-Contents: Trivial Double-Torus Knot by Chuichiro Hayashi On Weight Systems Derived from Heisenberg Lie Algebras by Hideaki Nishihara Link Invariant for the Spinor Representation of by Bertrand Patureau-Mirand Alexander Polynomial of Sextics by Mutsuo Oka Diagrammatic Unknotting of Knots and Links in the Projective Space by Maciej Mroczkowski Quantum Invariants of Templates by Louis H. Kauffman, Masahico Saito and Michael C. Sullivan Thinning Genus Two Heegaard Spines in S3 by Martin Scharlemann and Abigail Thompson The Linear Growth in the Lengths of a Family of Thick Knots by Y. Diao, C. Ernst and M. Thistlethwaite A Move on Diagrams that Generates S-Equivalence of Knots by Swatee Naik and Theodore Stanford If you are interested in submitting your work to JKTR for publication, please visit http://www.worldscinet.com/jktr/mkt/guidelines.shtml to learn how. The Editorial Board JKTR === Subject: thank you! Epigone-thread: roahaithang Originator: israel@math.ubc.ca (Robert Israel) Arturo Magidin's example is very instructive. It perfectly demonstrates the difference between a prime element and an irreducible element. (I knew such examples only for non-integral domains.) The lack of uniqueness of factorization is very unusual phenomenon. Still thinking over it... === Subject: preimage of a curve inside its Jacobian Epigone-thread: yelkrermgung Originator: israel@math.ubc.ca (Robert Israel) I cannot find a reference for the follwing result which I was told to be true; it should hold over any (say perfect or char 0) field: consider a curve C inside its Jacobian J, and an endomorphism T:J-->J of the Jacobian J. Then the preimage T^(-1)(C) is irreducible. Would it be true if instead of curve we take a variety of any dimension ? Then we refumulate this as If W lies in an Abelian variety A and W does not lie in any proper Abelian subvariety of A, and T is an endomorphism of the Abelian variety A, then, as before, the preimage T^(-1) W is irreducible. === Subject: probabilistic approach to riemann hypothesis Originator: israel@math.ubc.ca (Robert Israel) I want to notify the forum of two papers on the riemann hypothesis: http://maa.org/features/chaitin.html 2) My brief note which discusses and extends Chaitin's idea to attempt to prove the RH by using probablistic methods at http://arXiv.org/abs/math.GM/0309148 Enjoy! Craig === Subject: EigenVECTOR statistics of random Hermitian matrices. Epigone-thread: rexphonggen Originator: israel@math.ubc.ca (Robert Israel) It seems that in the study of random matrices (GUE, GSE, GOE), that the main matter of interest is the pairwise correlation function of the eigenvalues. Has anyone figured out any kind of correlation function of the elements of the eigenvectors? A paper by Chalker and Mehlig on the xxx.lanl.gov server indicates that the random matrix eigenvector statistics for the GUE, for example, are determined by the Haar measure that leaves the ensemble invariant. I have some idea of what a Haar measure is, but I found this to be a very cryptic remark. Is there any kind of explicit formula concerning the statistics of the eigenvector of a random Hermitian matrix? Any help would be appreciated. === Subject: Braid representation of knots Originator: israel@math.ubc.ca (Robert Israel) It is known any knot can be represented by a 2n braid. Does the following hold? To each n, there is a knot that can't be represented by a 2i braid with iIt is known any knot can be represented by a 2n braid. Does your restriction to even numbers mean you want to use the plat representation, rather than the closed braid representation? The answer doesn't really matter, because on either interpretation the answer to your question below is yes. >Does the following hold? >To each n, there is a knot that can't be represented >by a 2i braid with iarbitrarily complicated.) Phrases to search on are bridge number (originally defined independently of braids, later shown--see Joan Birman's book on braids--to be half the minimum [even] number of strings in a plat representation) and braid index (the minimum number of strings in a closed braid reprsentation; sometimes called string index or braid number, but I prefer braid index and would like to popularize brin(K) as a standard notation for it, since it's mnemonic in English and `brin' is the French word for `string' [in the context of braids, at least]). Lee Rudolph === Subject: book on representation theory Originator: israel@math.ubc.ca (Robert Israel) Can somebody suggest a good book for a novice on representation theory of groups - particularly over characteristic zero fields. Most of the books i tried looking at, assume algebraically closed fields for some important results. I am interested in representations over an arbitrary number field. Kiran === Subject: Re: category question Originator: israel@math.ubc.ca (Robert Israel) >Is there a term for a category whose morphisms can be expressed in >terms of composion through a single object? Namely, there's an object >A in the category such that for objects B and C, Hom(B,C) is Hom(B,A) >composed with Hom(A,C). Ie, the morphisms to and from A generate all >morphisms in the category. I'm also looking for a more general >version, a category where the morphisms to and from a finite set of >objects generate the morphisms in the category. Any help included >you. by the way was my answer of any help? it was sort of a joke answer (because i thought that the way that you described the property turned out to be equivalent to a rather differently stated property related to karoubi envelope aka splitting idempotents completion aka generalized cauchy completion of a category) but it was also intended to be serious and hopefully helpful. anyway i hope that my answer was at least factually correct. -- [e-mail address jdolan@math.ucr.edu] === Subject: Re: category question Originator: israel@math.ubc.ca (Robert Israel) |to karoubi envelope aka splitting idempotents completion aka |generalized cauchy completion of a category) but it was also 1. sorry; i accidentally posted what i'd intended as e-mail. 2. now that i think about it i think the name generalized cauchy completion is the name of a different but related completion process on categories of some kind, but i don't remember the details. -- [e-mail address jdolan@math.ucr.edu] === Subject: Re: category question Originator: israel@math.ubc.ca (Robert Israel) >Is there a term for a category whose morphisms can be expressed in >terms of composion through a single object? Namely, there's an object >A in the category such that for objects B and C, Hom(B,C) is Hom(B,A) >composed with Hom(A,C). Ie, the morphisms to and from A generate all >morphisms in the category. I'm also looking for a more general >version, a category where the morphisms to and from a finite set of >objects generate the morphisms in the category. Any help included >you. > by the way was my answer of any help? it was sort of a joke answer > (because i thought that the way that you described the property turned > out to be equivalent to a rather differently stated property related > to karoubi envelope aka splitting idempotents completion aka > generalized cauchy completion of a category) but it was also > intended to be serious and hopefully helpful. anyway i hope that > my answer was at least factually correct. I think so. Currently, I'm brushing up on my math for a comprehensive exam at UC Davis in a couple of weeks so I really won't be able to look at this till after that exam. But the little I was able to do does indicate that this is similar in interesting ways to what I was Peter Hines also did some interesting work in the area (his categories rely at some points on this property) for his dissertation and was kind enough to point me to that work. Karl Hallowell khallow@hotmail.com === Subject: Maps on surfaces of Euler characteristic -7. Originator: israel@math.ubc.ca (Robert Israel) with three-and-a-half handles, (projective plane with 3 handles), admits holocontiguous maps of exactly 10 regions. (Dually, an embedded K_10 graph.) Exact in the sense that each region borders each other one *exactly* once; (just as the torus so admits 7 regions). I am keen to see examples:- I have many of my own, but would like to see others (coded into any obvious database), to get some idea of how many might be the total number of distinct such maps. (It must be finite.) Does anyone have any? Maps with 9 regions on the surface with EC = -5 would also be welcome; though I'm fairly sure there are only two of these, (closely related). Anyway, if anyone has data for maps of either sort, please let me know. ---------------------------------------------------------------------------- -- Bill Taylor W.Taylor@math.canterbury.ac.nz ---------------------------------------------------------------------------- -- Every nation ridicules other nations, and they are all right. ---------------------------------------------------------------------------- -- === Subject: transcendence bases (can't understand proof) Epigone-thread: casnemsil Originator: israel@math.ubc.ca (Robert Israel) I am trying to understand the proof of the following result: Let K < E < F be field extensions. Let M be a transcendence basis of E over K, and N be a transcendence basis of F over E. Then Mcap N is empty, and Mcup N is a transcendence basis of F over K. In section 75 of van der Waerden's Algebra, there is a proof of similar statement. In the proof there is a paragraph (notation slightly changed): The field F is algebraic over E(N), E is algebraic over K(M); HENCE F is algebraic over K(M,N). I can't understand this hence. We see that there is the following series of fields: K -- K(M) -- E -- E(N) -- F All we need to establish, is that any element from F is a root of some polynomial with coefficients from K(M,N). How one can do it? In Bourbaki's Algebra, Ch. V, S.5 the exposition is more eloquent, but also leaves some discontent: E(N) is algebraic over K(Mcup N)=K(M)(N), since 1) E(N)=K(Mcup N)(E) and 2) every element of E is algebraic over K(M) hence over K(Mcup N) [reference]. Thus, F is algebraic over K(Mcup N) [reference]. Here I managed to persuade myself that all the reasoning is valid. Namely, from 1) E(N) is being obtained from K(Mcup N) by adjoining roots of polynomials (since E is algebraic over K(Mcup N)), hence E(N) is algebraic over K(Mcup N). But is it possible to show directly, taken an arbitrary element x from E(N), that x is a root of some polynomial over K(Mcup N)? === Subject: Parameterizing the solution of det(xy(x+y+I)) > 0 Originator: israel@math.ubc.ca (Robert Israel) Let (X,Y) be the collection of solutions to Det(xy(x+y+I)) > 0. Does it exist a homeomorphism that map (X,Y) to a simple set (say some subset of (phi, theta) such that Det(phi)*Det(theta) > 0) ? Any suggestion on how to approach this problem will be greatly appreciated. K. Yam === Subject: Visualizations of Modular Forms Originator: israel@math.ubc.ca (Robert Israel) I'm looking to visualize a modular form. Might there be a link to === Subject: real plane curve question Originator: israel@math.ubc.ca (Robert Israel) Suppose that f(x,y) is a polynomial of degree n over the reals, and suppose that the line y=a meets the curve f(x,y)=0 in n points. It is elementary that y=a meets f_x (the partial derivative of f with respect to x) in n-1 points. Question: What conditions on f imply that the line y=a also meets f_y (the partial derivative of f with respect to y) in n-1 points? Steve === Subject: naturally optimal linear systems Originator: israel@math.ubc.ca (Robert Israel) I have the following basic linear system: dot{x} = A times x + B times f(t) with x a vector, A and B matrices, and f(t) a time-varying signal. It's easy to figure out what the signal f has to be in order to force the system to minimize an optimality condition integral{x^{T} times Q times x + f^{T} times R times F dt} However, I want to do the reverse, i.e. I'm interested in the conditions under which one can construct a cost functional which the linear system naturally minimizes. Is this possible in general, or even under some restricted set of conditions? Glen ____________________________________________________________ Dr. Glen Henshaw Naval Center for Space Technology U.S. Naval Research Laboratory (202) 767-1196 === Subject: Signal synthesis from Wigner-Ville distribution Originator: israel@math.ubc.ca (Robert Israel) I have some problems with this question. Can anybody help me? I'm trying to recover signal from Wigner-Ville distribution after time-frequency filtering. I base on Spatial and Time-Frequency Signature Estimation of Nonstationary Sources paper [Moeness] (found in internet). The procedures from this paper work as follows: 1. Calculate Wigner-Ville distribution; WVD(t,f) = sum[ x(t+k/2)*x'(t-k/2)*exp(-jkf) ] 2. Filter WVD as you need WVD'(t,f) = WVD(t,f)*G(t,f) where G(t,f) - binary mask (0,1) 3. Take the inverse Fast Fourier Transform of WVD' P(t,n) = IFFT( WVD' ) 4. Construct the matrix Q with Q(i,j) = P( (i+j)/2 , i-j ) 5. Apply eigen-decomposition to the matrix Q and obtain the maximum eigenvalue and associated eigenvector. Now recovered signal should be based on this eigenvector. And now my computation: i.e. signal: sig=[1 2 3 4 5 6 7 1] (WVD should obtained from signal transformed by Hilbert Transform, but I want to make it easier) WVD = Columns 1 through 7 1.0000 10.0000 35.0000 84.0000 119.0000 114.0000 61.0000 1.0000 8.2426 20.3137 27.3137 56.1127 85.4975 57.4853 1.0000 4.0000 -1.0000 -8.0000 -17.0000 28.0000 49.0000 1.0000 -0.2426 -2.3137 4.6863 -6.1127 -13.4975 40.5147 1.0000 -2.0000 3.0000 -4.0000 15.0000 -26.0000 37.0000 1.0000 -0.2426 -2.3137 4.6863 -6.1127 -13.4975 40.5147 1.0000 4.0000 -1.0000 -8.0000 -17.0000 28.0000 49.0000 1.0000 8.2426 20.3137 27.3137 56.1127 85.4975 57.4853 Column 8 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 2. I'm going to do this without mask to make it easier 3. My inwerse transform P= Columns 1 through 7 1.0000 4.0000 9.0000 16.0000 25.0000 36.0000 49.0000 0 3.0000 8.0000 15.0000 24.0000 35.0000 6.0000 0 0 5.0000 12.0000 21.0000 4.0000 0 0 0 0.0000 7.0000 2.0000 0 0.0000 0 0 0 0 0 0 0 0 0 0.0000 7.0000 2.0000 0 0.0000 0 0 5.0000 12.0000 21.0000 4.0000 0 0 3.0000 8.0000 15.0000 24.0000 35.0000 6.0000 Column 8 1.0000 0 0 0 0 0 0 0 4. And in the end Q-matrix Q= Columns 1 through 7 2.0000 0 3.0000 0 5.0000 0 7.0000 0 8.0000 0 8.0000 0 12.0000 0 3.0000 0 18.0000 0 15.0000 0 21.0000 0 8.0000 0 32.0000 0 24.0000 0 5.0000 0 15.0000 0 50.0000 0 35.0000 0 12.0000 0 24.0000 0 72.0000 0 7.0000 0 21.0000 0 35.0000 0 98.0000 0 2.0000 0 4.0000 0 6.0000 0 Column 8 0 2.0000 0 4.0000 0 6.0000 0 2.0000 5. After that eigenvectors/eigenvalues are copmputed by Matlab, so it's no problem The results obtained as above are not satisfied for me because when I try to use filtering the recovered signal is not correct in time domain. I think WVD and P matrix are computed correctly but I'm not sure about Q-matrix. Has anybody use this method and can help to solve my problem? Maybe you know another method that work in signal synthesis from Wigner-Ville distribution? I'll be grateful for any help. Krzys kidzkows@elka.pw.edu.pl === Subject: Resource Bounded Unprovability of Computational Lower Bounds Originator: israel@math.ubc.ca (Robert Israel) Readers of this newsgroup may fing this preprint by of interest an worthy of discussion: Resource Bounded Unprovability of Computational Lower Bounds Tatsuaki Okamoto and Ryo Kashima Abstract. This paper shows that no polynomial-time Turing machine can produce a proof (based on a reasonable theory including Peano Arithmetic) of a super-polynomial-time lower bound of an NP (or more generally, PSPACE) problem. In other words, no polynomial-time Turing machine can produce a proof of ``P $not=$ NP''. Therefore, {it to prove ``P $not=$ NP''} (by any technique and any reasonable theory) {it requires super-polynomial-time computational power}. This result is a kind of generalization of the result of ``Natural Proofs'' by Razborov and Rudich, who showed that to prove ``P $not=$ NP'' by a class of techniques called ``Natural'' implies computational power that can break a typical cryptographic primitive, a pseudo-random generator. This result also implies that {it there is no (finite-size) formal proof for ``P $not=$ NP''} in any reasonable theory. This is considered to be a generalization of the result by Baker, Gill and Solovay,*@ who showed that there is no relativizable proof for ``P $not=$ NP''. Based on this result, we show that {it the security of any computational cryptographic scheme is unprovable} in the standard setting of modern cryptography, where an adversary is modeled as a polynomial-time Turing machine. Category / Keywords. foundations / Contact author: Tatauaki Okamoto (okamoto@isl.ntt.co.jp) Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation __________________________________________________________________________ __________________________________ Professor Michael Anshel Department of Computer Sciences R8/206 The City College of New York New York,New York 10031 http://www-cs.engr.ccny.cuny.edu/~csmma/ csmma@cs.ccny.cuny.edu MikeAt1140@aol.com === Subject: The Analytic Continuation of the HyperPower function Originator: israel@math.ubc.ca (Robert Israel) The LambertW can be used to solve a couple of interesting problems, including some relating to the fixed points of the hyperpower sequence x^x^x^... Turns out there is another bonus in there, that's again using the LambertW, this time to define the analytic continuation of the real hyperpower function F(x) = x^x^x^... investigation, but the idea that it could be used as the analytic continuation of F(x) hadn't occured to me, until two days ago. There is also a nice investigation of the two components of the Hopf bifurcation using Maple, and some code to sketch the branches in (0,e^(-e)) , in my math section: Enjoy. -- Ioannis http://users.forthnet.gr/ath/jgal/ ___________________________________________ Eventually, _everything_ is understandable. === Subject: alternative to Cantor set Originator: israel@math.ubc.ca (Robert Israel) anyone who have a glimpse into the point set structure theory will know that Cantor set is endowed with the following properties: 1.nowhere dense in R^1; 2.of Lebesgue measure zero; 3.is a (nonempty)complete set; 4.If we have the following subset of real numbers for a given set A: D(A)={s: s=d(a.b), a,b as members of A} then the Cantor set G satisfies D(G)=[0,1], i.e. for any 0<=s<=1, there exist a,b as members of G, s.t. s=d(a,b). I have paid some effort on finding another subset of [0,1] satisfying the above four properties but fails. Can anyone offer one? Bill === Subject: Re: alternative to Cantor set Originator: israel@math.ubc.ca (Robert Israel) > anyone who have a glimpse into the point set structure theory will > know that Cantor set is endowed with the following properties: > 1.nowhere dense in R^1; > 2.of Lebesgue measure zero; > 3.is a (nonempty)complete set; > 4.If we have the following subset of real numbers for a given set A: > D(A)={s: s=d(a.b), a,b as members of A} > then the Cantor set G satisfies > D(G)=[0,1], i.e. for any 0<=s<=1, there exist a,b as members of G, > s.t. > s=d(a,b). > I have paid some effort on finding another subset of [0,1] satisfying > the above four properties but fails. Can anyone offer one? > Bill How about the set of all numbers in [0,1] which have a base 5 expansions using only the digits {0,2,4}? -- G. A. Edgar http://www.math.ohio-state.edu/~edgar/ === Subject: Call for book proposals - Series on University Mathematics Originator: israel@math.ubc.ca (Robert Israel) For the advancement of science and civilization, there is always the problem of creativity and education. Without creativity, the sciences and civilization would stagger and decline. Without widespread education effort, human talents would be wasted and the creative processes would halt. The aim of the Series on University Mathematics is to publish educational books written by creative mathematicians for undergraduate and graduate students as well as the general public, helping them to understand and enjoy modern and advanced mathematics. To contribute to this series, please email editor@worldscientific.com or visit http://www.wspc.com/books/series/scor_series.shtml thank you, The Editors Series on University Mathematics === Subject: This week in the mathematics arXiv (25 Aug - 29 Aug) Originator: israel@math.ubc.ca (Robert Israel) Here are this week's titles in the mathematics arXiv, available at: http://front.math.ucdavis.edu/ http://front.math.ucdavis.edu/submissions This week in the mathematics arXiv may be freely redistributed with attribution and without modification. Titles in the mathematics arXiv (25 Aug - 29 Aug) ------------------------------------------------- AC: Commutative Algebra ----------------------- math.AC/0308272 Jooyoun Hong: Rees Algebras of Conormal Modules math.AC/0308264 Sara Faridi: Simplicial Trees are Sequentially Cohen-Macaulay math.AC/0308263 Samuel Wuthrich: Homology of powers of regular ideals AG: Algebraic Geometry ---------------------- math.AG/0308266 Kiumars Kaveh: Fixed Points of Torus Action and Cohomology Ring of Toric Varieties math.AG/0308247 Thomas Keilen: Smoothness of Equisingular Families of Curves math.AG/0308233 John Hubbard, Victor H. Moll: A geometric view of rational Landen transformations math.AG/0308221 Philip Boalch: The Klein solution to Painleve's sixth equation math.AG/0308218 Megumi Harada, Nicholas J. Proudfoot: Hyperpolygon spaces and their cores math.AG/0308216 Tom Braden: Koszul duality for toric varieties math.AG/0308212 St'ephane Druel: Caract'erisation de l'espace projectif math.AG/0308209 Kefeng Liu, Andrey Todorov, Shing-Tung, Kang Zuo: Shafarevich's Conjecture for CY Manifolds I math.AG/0308208 Nero Budur, Marta Casanellas, Elisa Gorla: Hilbert functions of irreducible arithmetically Gorenstein schemes AP: Analysis of PDEs -------------------- math.AP/0308278 Andrew Hassell, Jared Wunsch: On the structure of the Schrodinger propagator math.AP/0308220 Steve Zelditch: Billiards and boundary traces of eigenfunctions math.AP/0308214 N. Burq, P. Gerard, N. Tzvetkov: Bilinear Eigenfunction Estimates and the Nonlinear Schroedinger Equation on Surfaces AT: Algebraic Topology ---------------------- cond-mat/0308530 Lucjan Jacak, Piotr Sitko, Konrad Wieczorek, Arkadiusz W'ojs: Quantum Hall Systems: Braid groups, composite fermions, and fractional charge math.AT/0308253 Matthias Franz: On the integral cohomology of smooth toric varieties math.AT/0308246 Regis Pellissier: Weak enriched categories - Categories enrichies faibles math.AT/0308243 Barbu Berceanu, Martin Markl, Stefan Papadima: Multiplicative models for configuration spaces of algebraic varieties CA: Classical Analysis and ODEs ------------------------------- math.CA/0308211 A.A. Korenovskyy, A.K. Lerner, A.M Stokolos: On multidimensional F. Riesz's Rising Sun Lemma CO: Combinatorics ----------------- math.CO/0308280 Mike Develin, Seth Sullivant: Markov bases of binary graph models math.CO/0308265 Thomas Lam: Growth diagrams, Domino insertion and Sign-imbalance cond-mat/0308515 Sergio Caracciolo, Andrea Sportiello: General duality for abelian-group-valued statistical-mechanics models math.CO/0308234 Marcos Kiwi, Martin Loebl, Jiri Matousek: Expected length of the longest common subsequence for large alphabets DG: Differential Geometry ------------------------- math.DG/0308283 Joseph A. Wolf: Complex Forms of Quaternionic Symmetric Spaces math.DG/0308279 Anna Pratoussevitch: Fundamental Domains in Lorentzian Geometry hep-th/0308141 Jos'e Figueroa-O'Farrill, Teruhiko Kawano, Satoshi Yamaguchi: Parallelisable Heterotic Backgrounds math.DG/0308249 Xianzhe Dai: A Positive Mass Theorem for Spaces with Asymptotic SUSY Compactification math.DG/0308244 C. Bartocci, I. Mencattini: Hyper-symplectic structures on integrable systems math.DG/0308241 Vestislav Apostolov, Tedi Draghici, Andrei Moroianu: The odd-dimensional Goldberg Conjecture math.DG/0308235 Jouko Mickelsson: Gerbes on quantum groups math.DG/0308232 Denis Kochan: Pseudodifferential forms and supermechanics math.DG/0308227 D.D.Porosniuc: A locally symmetric Kaehler Einstein structure on the cotangent bundle of a space form math.DG/0308217 Aristide Tsemo: Affine manifolds, lagrangian manifolds math.DG/0308215 Brian Dean: Compact Embedded Minimal Surfaces of Positive Genus Without Area Bounds DS: Dynamical Systems --------------------- math.DS/0308252 Toshiaki Fujiwara, Richard Montgomery: Convexity in the Figure Eight Solution to the Three-Body Problem math.DS/0308223 Nguyen T. Thao, C. Sinan Gunturk: Ergodic Dynamics in Sigma-Delta Quantization: Tiling Invariant Sets and Spectral Analysis of Error FA: Functional Analysis ----------------------- math.FA/0308273 Sever Silvestru Dragomir: Reverses of Schwarz, Triangle and Bessel Inequalities in Inner Product Spaces math.FA/0308270 S.S. Dragomir, Y.J. Cho, S.S. Kim, A. Sofo: Some Boas-Bellman Type Inequalities in 2-Inner Product Spaces math.FA/0308251 Eric Weber: The Geometry of Sampling on Unions of Lattices math.FA/0308250 Akram Aldroubi, David Larson, Wai-Shing Tang, Eric Weber: Geometric Aspects of Frame Representations of Abelian Groups math.FA/0308240 Victor Shulman, Lyudmila Turowska: Operator synthesis. I. Synthetic sets, bilattices and tensor algebras math.FA/0308226 Thomas William Dawson: Extensions of Normed Algebras GN: General Topology -------------------- math.GN/0308236 A. Chigogidze, V. Valov: Extraordinary dimension of maps math.GN/0308219 H. Murat Tuncali, E. D. Tymchatin, Vesko Valov: Extensional dimension and completion of maps GT: Geometric Topology ---------------------- math.GT/0308277 Louis H. Kauffman, Nikolai A. Krylov: Kernel of the variation operator and periodicity of the open books math.GT/0308276 Tolga Etgu, B. Doug Park: Symplectic tori in rational elliptic surfaces math.GT/0308274 Koji Fujiwara, Takashi Shioya, Saeko Yamagata: Parabolic isometries of CAT(0) spaces and CAT(0)-dimensions math.GT/0308268 Francis Bonahon, Xiaodong Zhu: The metric space of geodesic laminations on a surface II: small surfaces math.GT/0308267 Xiaodong Zhu, Francis Bonahon: The metric space of geodesic laminations on a surface. I math.GT/0308222 Riccardo Piergallini, Daniele Zuddas: A universal ribbon surface in B^4 hep-th/0308152 Kazuhiro Hikami, Anatol N. Kirillov: Torus Knot and Minimal Model MG: Metric Geometry ------------------- math.MG/0308262 Joseph Corneli, Paul Holt, George Lee, Nicholas Leger, Eric Schoenfeld, Benjamin Steinhurst: The Double Bubble Problem on the Flat Two-Torus math.MG/0308254 Mike Develin, Bernd Sturmfels: Tropical Convexity math.MG/0308239 Igor Rivin: Some observations on the simplex MP: Mathematical Physics ------------------------ math-ph/0308040 Raymond Brummelhuis, Mary Beth Ruskai: One-dimensional models for atoms in strong magnetic fields, II: Anti-Symmetry in the Landau Levels math-ph/0308039 V. V. Varlamov: Hyperspherical Functions and Harmonic Analysis on the Lorentz Group math-ph/0308038 V. V. Varlamov: Relativistic wavefunctions on the Poincare group math-ph/0308037 R. F. Streater: Duality in quantum information manifolds math-ph/0308036 P.J. Forrester, N.S. Witte: Discrete Painlev'e equations, Orthogonal Polynomials on the Unit Circle and $N$-recurrences for averages over U(N) -- PVI $tau$-functions math-ph/0308035 Guowu Meng: Legendre Transform, Hessian Conjecture and Tree Formula math-ph/0308034 Liudmila Joukovskaya, Yaroslav Volovich: Energy Flow from Open to Closed Strings in a Toy Model of Rolling Tachyon math-ph/0308033 F. Benatti, V. Cappellini, F. Zertuche: Quantum Dynamical Entropies in Discrete Classical Chaos math-ph/0308032 Kwang C. Shin: On half-line spectra for a class of non-self-adjoint Hill operators nlin.CD/0308026 J. Kaidel, M. Brack: Uniform approximations for pitchfork bifurcation sequences math-ph/0308031 Soeren Koester: Structure of Coset Models cond-mat/0308466 Malte Henkel, Gunter Schutz: On the universality of the fluctuation-dissipation ratio in non-equilibrium critical dynamics math-ph/0308030 J.E. Avron: Colored Hofstadter butterflies math-ph/0308029 Yasuyuki Kawahigashi: Classification of operator algebraic conformal field theories in dimensions one and two math-ph/0308028 Bergthor Hauksson, Jakob Yngvason: Asymptotic Exactness of Magnetic Thomas-Fermi Theory cond-mat/0112325 Y. M. Cho: Creation of Knots in Two-component Bose-Einstein Condensates cond-mat/0308182 Y. M. Cho, H. J. Khim: Non-Abelian Vortices in Condensed Matter math-ph/0308027 Shigeki Matsutani: Relations in a Loop Soliton as a Quantized Elastica math-ph/0308026 Bindu A. Bambah: Polynomial Algebras and their Applications NT: Number Theory ----------------- math.NT/0308213 James McKee, Chris Smyth: There are Salem numbers of every trace OA: Operator Algebras --------------------- math.OA/0308271 Kenley Jung: A hyperfinite inequality for free entropy dimension math.OA/0308261 Massoud Amini: Tannaka-Krein duality for compact groupoids III, duality theory math.OA/0308260 Massoud Amini: Tannaka-Krein duality for compact groupoids II, Fourier transform math.OA/0308259 Massoud Amini: Tannaka-Krein duality for compact groupoids I, representation theory math.OA/0308258 Massoud Amini, Alireza Medghalchi: Restricted algebras on inverse semigroups III, Fourier algebra math.OA/0308257 Massoud Amini, Alireza Medghalchi: Restricted algebras on inverse semigroups II, positive definite functions math.OA/0308256 Massoud Amini, Alireza Medghalchi: Restricted algebras on inverse semigroups I, representation theory math.OA/0308255 Gero Fendler: Simplicity of the reduced C-*-algebras of certain Coxeter groups math.OA/0308245 Michael Skeide: Independence and Product Systems math.OA/0308231 Michael Skeide: Commutants of von Neumann Modules, Representations of B^a(E) and Other Topics Related to Product Systems of Hilbert Modules math.OA/0308230 Michael Skeide: Von Neumann Modules, Intertwiners and Self-Duality math.OA/0308207 Marc A. Rieffel: Compact Quantum Metric Spaces PR: Probability Theory ---------------------- math.PR/0308282 Vlada Limic, Robin Pemantle: More rigorous results on the Kauffman-Levin model of evolution math.PR/0308242 Patrik L. Ferrari, Herbert Spohn: Constrained Brownian motion: fluctuations away from circular and parabolic barriers math.PR/0308238 Peter Friz, Nicolas Victoir: Approximations of the Brownian Rough Path with Applications to Stochastic Analysis cond-mat/0308508 D. Gabrielli, A. Galves, D. Guiol: Fluctuations of the Empirical Entropies of a Chain of Infinite Order math.PR/0308237 Veronique Ladret: Asymptotic hitting time for a simple evolutionary model of protein folding QA: Quantum Algebra ------------------- math.QA/0308281 Stephen F. Sawin: Quantum Groups at Roots of Unity and Modularity math.QA/0308275 Alain Connes, Michel Dubois-Violette: Moduli space and structure of noncommutative 3-spheres math.QA/0308269 Edward Frenkel: Opers on the projective line, flag manifolds and Bethe Ansatz math.QA/0308248 Yi-Zhi Huang, Liang Kong: Open-string vertex algebras, tensor categories and operads math.QA/0308229 Konrad Schmuedgen, Elmar Wagner: Hilbert space representations of cross product algebras II math.QA/0308228 Nicolas Andruskiewitsch, Sonia Natale: Double categories and quantum groupoids SG: Symplectic Geometry ----------------------- math.SG/0308225 Cheol-Hyun Cho, Yong-Geun Oh: Floer cohomology and disc instantons of Lagrangian torus fibers in Fano toric manifolds math.SG/0308224 Cheol-Hyun Cho: Holomorphic disc, spin structures and Floer cohomology of the Clifford torus math.SG/0308210 Andrey Todorov: Large Radius Limit and SYZ Fibrations of Hyper-Kahler Manifolds -- / Greg Kuperberg (UC Davis) / / Visit the Math ArXiv Front at http://front.math.ucdavis.edu/ / * All the math that's fit to e-print * === Subject: Interesting foundational issues - FOM discussion Originator: israel@math.ubc.ca (Robert Israel) A recent discussion - triggered by M J Murphy's post of 20th August on The Goedel sentence in the Foundations of Mathematics (FOM) Forum - highlighted a wide range of foundational issues that should be of interest to some readers of this group. As seems almost inevitable when the standard interpretation of Goedel's reasoning in his famous 1931 paper, On formally undecidable propositions of Principia Mathematica and related systems I, is the subject of a multi-disciplinary discussion, issues tend to gravitate frustratingly into a semantic cul-de-sac. However, if one persists till the diversionary element - invariably, the apparent incongruity of true but unprovable sentences - clears away, then significant issues emerge that may remain obscured otherwise. It is fascinating to note that these issues overwhelmingly indicate the need for an overdue resolution of a number of concepts, centered essentially around the need for a more effective verifiability of the concept of mathematical truth than that offered currently by classical theory. The need for such resolution seems to be increasingly felt, and demanded from logicians, by disciplines that look to mathematics not only for expressing their concepts precisely, but more importantly for communicating these concepts effectively, and unambiguously, to others - both inside and outside a discipline. But first, to avoid the most common semantic diversion, it is essential to note that - despite the current lack of an effective method for verifying the truth of an arbitrary Arithmetic proposition such as (Ax)F(x) - there is nothing particularly mysterious or esoteric about the fact that a particular Arithmetic proposition, say (Ax)R(x), can be constructively asserted as Tarskian-true from the axioms of the Arithmetic, but not as proof-sequentially provable from the axioms of the Arithmetic by the classical deduction rules of the Arithmetic. It simply means that some Arithmetic propositions can be meaningfully, and constructively, assigned one each of two, not entirely unrelated, sets of properties - truth/falsity and provability/unprovability - that are not, however, equivalent. More precisely, what Goedel proved (by an intuitionistically unobjectionable meta-proof) was that there is a relation R(x), constructively definable in any recursively defined axiomatic Arithmetic of the natural numbers (whether this is considered as a formal system or the standard interpretation of such a system) such that R(n) is provable for any natural number n (in the sense that, given any natural number n, there is always a classical, constructive, proof sequence/deduction for R(n) from the axioms of the Arithmetic by the classical deduction rules of the Arithmetic). By classical definitions of the truth of number-theoretic relations (formally expressed by Tarski's definitions), this property of R(x) is conventionally expressed symbolically as the meta-assertion that (Ax)R(x) is a constructively established true arithmetic assertion. However, since Goedel also proved, again constructively, that there is no classical, constructive, proof sequence - consisting of only statements within the Arithmetic - from which the symbolic expression (Ax)R(x) can be mechanically (i.e. without interpreting any of the statements using Tarski's definitions) deduced, and so termed as provable from the axioms of the Arithmetic by the classical deduction rules of the Arithmetic, he (arguably unfortunately) expressed this asymmetry as the meta-assertion that (Ax)R(x) is a true, but unprovable, proposition of the Arithmetic. Now, the wider significance of Goedel's reasoning does not lie in whether, or even why, the particular Arithmetic proposition (Ax)R(x) - that he defined constructively - is true but unprovable in the Arithmetic in question. It lies, rather, in the fact that, firstly, if any proposition (Ax)F(x) were provable in the Arithmetic, then there would be a uniform effective method, say EM_Alpha, necessarily independent of n, that, given any natural number n, would constructively prove that F(n) holds in the Arithmetic; and, secondly, in the fact that, if (Ax)F(x) were Tarskian-true, then, given any natural number n, there would always be some individual effective method, say EM_Beta(n) - not necessarily independent of n - that would constructively prove that F(n) holds in the Arithmetic (assuming that Tarski's definitions implicitly imply the existence of an effective method - not necessarily algorithmic - for verifying the truth of a proposition under the standard interpretation). Clearly, whilst the former implies the latter, the first half of Goedel's proof of Theorem VI in his 1931 paper can be reasonably interpreted as asserting, essentially, that the converse does not hold if we assume the consistency of the Arithmetic in question. Now the interesting foundational issue here is, firstly, whether, and under what conditions, EM_Alpha can be taken to be, say, a Markov algorithm; and, secondly, whether, and under what conditions, the existence of EM_Alpha for a given F(x) would imply that (Ax)F(x) is provable. Of interest, similarly, would be the question of whether the Tarskian-truth of a proposition (Ax)F(x) under any interpretation can be qualified as holding if, and only, if, given any value s in the range of the interpretation, there is an effective method in the interpretation for determining that F(s) holds. In other words, can, and if so how and under what conditions, Tarskian-truth be made effectively verifiable in any interpretation of an Arithmetic (more particularly, in the standard interpretation of an Arithmetic such as, say, PA). Another interesting foundational issue raised in the discussion is the question of when, and under what conditions, we may assert that a number-theoretic relation, and the standard interpretation of its formal expression in an Arithmetic such as PA, can be asserted as having the same meaning. A related, albeit obliquely raised, question is whether the PA-formula Con(PA), under the standard interpretation, asserts that PA is consistent by an arbitrary convention, or whether it can be shown to be equivalent to the formal meta-definition of classical consistency in a constructive, and intuitionistically unobjectionable way (in Goedel's sense). Yet another intriguing, also obliquely raised, foundational issue, is whether, and under what conditions, a number-theoretic relation - and its defining expressions - can be introduced axiomatically into a formal Arithmetic such as PA, so that it directly supports reference to its own syntax. In other words, can we effectively, and meaningfully, define a mathematical object; and under what conditions can we introduce such objects into a formal system such as PA, or into a set theory such as ZFC, etc. without inviting inconsistency? Another, again obliquely raised, issue is that if PA and its standard interpretation SI are to be treated as different languages, how are they related? Since, despite the misleading semantics, PA is essentially intended to formalise SI, which should be considered the more fundamental? Are there any conditions under which PA could be considered a constructive interpretation of SI? Bhupinder Singh Anand