Showing 1–50 of 57 results for author: Weaver, N

Extracting Godl [sic] from the Salt Mines: Ethereum Miners Extracting Value

Authors: Julien Piet, Jaiden Fairoze, Nicholas Weaver

Abstract: Cryptocurrency miners have great latitude in deciding which transactions they accept, including their own, and the order in which they accept them. Ethereum miners in particular use this flexibility to collect MEV-Miner Extractable Value-by structuring transactions to extract additional revenue. Ethereum also contains numerous bots that attempt to obtain MEV based on public-but-not-yet-confirmed t… ▽ More Cryptocurrency miners have great latitude in deciding which transactions they accept, including their own, and the order in which they accept them. Ethereum miners in particular use this flexibility to collect MEV-Miner Extractable Value-by structuring transactions to extract additional revenue. Ethereum also contains numerous bots that attempt to obtain MEV based on public-but-not-yet-confirmed transactions. Private relays shelter operations from these selfsame bots by directly submitting transactions to mining pools. In this work, we develop an algorithm to detect MEV exploitation present in previously mined blocks. We use our implementation of the detector to analyze MEV usage and profit redistribution, finding that miners make the lion's share of the profits, rather than independent users of the private relays. More specifically, (i) 73% of private transactions hide trading activity or re-distribute miner rewards, and 87.6% of MEV collection is accomplished with privately submitted transactions, (ii) our algorithm finds more than $6M worth of MEV profit in a period of 12 days, two thirds of which go directly to miners, and (iii) MEV represents 9.2% of miners' profit from transaction fees. Furthermore, in those 12 days, we also identify four blocks that contain enough MEV profits to make time-bandit forking attacks economically viable for large miners, undermining the security and stability of Ethereum as a whole. △ Less

Submitted 29 March, 2022; originally announced March 2022.

Hierarchies of Tarskian truth predicates

Authors: Nik Weaver

Abstract: Hierarchies of non self-applicative truth predicates take us beyond Gamma_0. Hierarchies of non self-applicative truth predicates take us beyond Gamma_0. △ Less

Submitted 1 February, 2022; originally announced February 2022.

Comments: 11 pages

nuSQuIDS: A toolbox for neutrino propagation

Authors: Carlos A. Argüelles, Jordi Salvado, Christopher N. Weaver

Abstract: The Neutrino Simple Quantum Integro-Differential Solver (nuSQuIDS) is a C++ code based on SQuIDS that propagates an ensemble of neutrinos through given media. Neutrino oscillation calculations relevant to current and next-generation experiments are implemented. This includes coherent and non-coherent neutrino interactions in settings such as the Sun, Earth, or a vacuum. The code is designed to be… ▽ More The Neutrino Simple Quantum Integro-Differential Solver (nuSQuIDS) is a C++ code based on SQuIDS that propagates an ensemble of neutrinos through given media. Neutrino oscillation calculations relevant to current and next-generation experiments are implemented. This includes coherent and non-coherent neutrino interactions in settings such as the Sun, Earth, or a vacuum. The code is designed to be accurate and flexible, while at the same time maintaining good performance. It has a modular design that allows the user to incorporate new physics in novel scenarios. △ Less

Submitted 27 December, 2021; originally announced December 2021.

Comments: 37 pages of main text and code manual appendix, 4 figures in text, 1 table in the main text. Code can be found at: https://github.com/arguelles/nuSQuIDS

Lipschitz Bernoulli utility functions

Authors: Efe A. Ok, Nik Weaver

Abstract: We obtain variants of the classical von Neumann-Morgenstern expected utility theorem, with and without the completeness axiom, in which the derived Bernoulli utility functions are Lipschitz. The prize space in these results is an arbitrary separable metric space, and the utility functions may be unbounded. The main ingredient of our results is a novel (behavioral) axiom on the underlying preferenc… ▽ More We obtain variants of the classical von Neumann-Morgenstern expected utility theorem, with and without the completeness axiom, in which the derived Bernoulli utility functions are Lipschitz. The prize space in these results is an arbitrary separable metric space, and the utility functions may be unbounded. The main ingredient of our results is a novel (behavioral) axiom on the underlying preference relations which is satisfied by virtually all stochastic orders. The proof of the main representation theorem is built on the fact that the completion of the Kantorovich-Rubinstein space is the canonical predual of the Banach space of Lipschitz functions that vanish at a fixed point. Two applications are given, one to the theory of non-expected utility theory, and the other to the theory of decision-making under uncertainty. △ Less

Submitted 22 April, 2021; originally announced April 2021.

Comments: 29 pages

MSC Class: 46N10; 91B06

Patient-specific fine-tuning of CNNs for follow-up lesion quantification

Authors: Mariëlle J. A. Jansen, Hugo J. Kuijf, Ashis K. Dhara, Nick A. Weaver, Geert Jan Biessels, Robin Strand, Josien P. W. Pluim

Abstract: Convolutional neural network (CNN) methods have been proposed to quantify lesions in medical imaging. Commonly more than one imaging examination is available for a patient, but the serial information in these images often remains unused. CNN-based methods have the potential to extract valuable information from previously acquired imaging to better quantify current imaging of the same patient. A pr… ▽ More Convolutional neural network (CNN) methods have been proposed to quantify lesions in medical imaging. Commonly more than one imaging examination is available for a patient, but the serial information in these images often remains unused. CNN-based methods have the potential to extract valuable information from previously acquired imaging to better quantify current imaging of the same patient. A pre-trained CNN can be updated with a patient's previously acquired imaging: patient-specific fine-tuning. In this work, we studied the improvement in performance of lesion quantification methods on MR images after fine-tuning compared to a base CNN. We applied the method to two different approaches: the detection of liver metastases and the segmentation of brain white matter hyperintensities (WMH). The patient-specific fine-tuned CNN has a better performance than the base CNN. For the liver metastases, the median true positive rate increases from 0.67 to 0.85. For the WMH segmentation, the mean Dice similarity coefficient increases from 0.82 to 0.87. In this study we showed that patient-specific fine-tuning has potential to improve the lesion quantification performance of general CNNs by exploiting the patient's previously acquired imaging. △ Less

Submitted 28 October, 2019; originally announced October 2019.

Hereditarily antisymmetric operator algebras

Authors: Nik Weaver

Abstract: We introduce a notion of ``hereditarily antisymmetric'' operator algebras and prove a structure theorem for them in finite dimensions. We also characterize those operator algebras in finite dimensions which can be made upper triangular and prove matrix analogs of the theorems of Dilworth and Mirsky for finite posets. Some partial results are obtained in the infinite dimensional case. We introduce a notion of ``hereditarily antisymmetric'' operator algebras and prove a structure theorem for them in finite dimensions. We also characterize those operator algebras in finite dimensions which can be made upper triangular and prove matrix analogs of the theorems of Dilworth and Mirsky for finite posets. Some partial results are obtained in the infinite dimensional case. △ Less

Submitted 20 April, 2019; v1 submitted 25 February, 2019; originally announced February 2019.

Comments: 34 pages; added a section to explain the physical interpretation

Journal ref: J. Inst. Math. Jussieu 20 (2021) 1039-1074

Cybercasing 2.0: You Get What You Pay For

Authors: Jaeyoung Choi, Istemi Ekin Akkus, Serge Egelman, Gerald Friedland, Robin Sommer, Michael Carl Tschantz, Nicholas Weaver

Abstract: Under U.S. law, marketing databases exist under almost no legal restrictions concerning accuracy, access, or confidentiality. We explore the possible (mis)use of these databases in a criminal context by conducting two experiments. First, we show how this data can be used for "cybercasing" by using this data to resolve the physical addresses of individuals who are likely to be on vacation. Second,… ▽ More Under U.S. law, marketing databases exist under almost no legal restrictions concerning accuracy, access, or confidentiality. We explore the possible (mis)use of these databases in a criminal context by conducting two experiments. First, we show how this data can be used for "cybercasing" by using this data to resolve the physical addresses of individuals who are likely to be on vacation. Second, we evaluate the utility of a "bride to be" mailing list augmented with data obtained by searching both Facebook and a bridal registry aggregator. We conclude that marketing data is not necessarily harmless and can represent a fruitful target for criminal misuse. △ Less

Submitted 15 November, 2018; originally announced November 2018.

Predicative well-ordering

Authors: Nik Weaver

Abstract: Confusion over the predicativist conception of well-ordering pervades the literature and is responsible for widespread fundamental misconceptions about the nature of predicative reasoning. This short note aims to explain the principal fallacy, first noted in [N. Weaver, Predicativity beyond Gamma_0, arXiv:math/0509244], and some of its consequences. Confusion over the predicativist conception of well-ordering pervades the literature and is responsible for widespread fundamental misconceptions about the nature of predicative reasoning. This short note aims to explain the principal fallacy, first noted in [N. Weaver, Predicativity beyond Gamma_0, arXiv:math/0509244], and some of its consequences. △ Less

Submitted 8 November, 2018; originally announced November 2018.

Comments: 7 pages

The Accuracy of the Demographic Inferences Shown on Google's Ad Settings

Authors: Michael Carl Tschantz, Serge Egelman, Jaeyoung Choi, Nicholas Weaver, Gerald Friedland

Abstract: Google's Ad Settings shows the gender and age that Google has inferred about a web user. We compare the inferred values to the self-reported values of 501 survey participants. We find that Google often does not show an inference, but when it does, it is typically correct. We explore which usage characteristics, such as using privacy enhancing technologies, are associated with Google's accuracy, bu… ▽ More Google's Ad Settings shows the gender and age that Google has inferred about a web user. We compare the inferred values to the self-reported values of 501 survey participants. We find that Google often does not show an inference, but when it does, it is typically correct. We explore which usage characteristics, such as using privacy enhancing technologies, are associated with Google's accuracy, but found no significant results. △ Less

Submitted 22 August, 2018; originally announced August 2018.

Report number: ICSI TR-16-003

The "quantum" Turan problem for operator systems

Authors: Nik Weaver

Abstract: Let V be a linear subspace of M_n(C) which contains the identity matrix and is stable under Hermitian transpose. A "quantum k-clique" for V is a rank k orthogonal projection P in M_n(C) for which dim(PVP) = k^2, and a "quantum k-anticlique" is a rank k orthogonal projection for which dim(PVP) = 1. We give upper and lower bounds both for the largest dimension of V which would ensure the existence o… ▽ More Let V be a linear subspace of M_n(C) which contains the identity matrix and is stable under Hermitian transpose. A "quantum k-clique" for V is a rank k orthogonal projection P in M_n(C) for which dim(PVP) = k^2, and a "quantum k-anticlique" is a rank k orthogonal projection for which dim(PVP) = 1. We give upper and lower bounds both for the largest dimension of V which would ensure the existence of a quantum k-anticlique, and for the smallest dimension of V which would ensure the existence of a quantum k-clique. △ Less

Submitted 20 February, 2018; originally announced February 2018.

Comments: 13 pages

The liar paradox is a real problem

Authors: Nik Weaver

Abstract: The liar paradox is widely seen as not a serious problem. I try to explain why this view is mistaken. The liar paradox is widely seen as not a serious problem. I try to explain why this view is mistaken. △ Less

Submitted 13 February, 2017; originally announced February 2017.

Comments: 10 pages. To appear in the Annals of the Japan Association for the Philosophy of Science

On the unique predual problem for Lipschitz spaces

Authors: Nik Weaver

Abstract: For any metric space X, the predual of Lip(X) is unique. If X has finite diameter or is complete and convex --- in particular, if it is a Banach space --- then the predual of Lip_0(X) is unique. For any metric space X, the predual of Lip(X) is unique. If X has finite diameter or is complete and convex --- in particular, if it is a Banach space --- then the predual of Lip_0(X) is unique. △ Less

Submitted 9 November, 2016; v1 submitted 6 November, 2016; originally announced November 2016.

Comments: 7 pages

Quantum measurable cardinals

Authors: David P. Blecher, Nik Weaver

Abstract: We investigate states on von Neumann algebras which are not normal but enjoy various forms of infinite additivity, and show that these exist on $B(H)$ if and only if the cardinality of an orthonormal basis of $H$ satisfies various large cardinal conditions. For instance, there is a singular countably additive pure state on $B(l^2(κ))$ if and only if $κ$ is Ulam measurable, and there is a singular… ▽ More We investigate states on von Neumann algebras which are not normal but enjoy various forms of infinite additivity, and show that these exist on $B(H)$ if and only if the cardinality of an orthonormal basis of $H$ satisfies various large cardinal conditions. For instance, there is a singular countably additive pure state on $B(l^2(κ))$ if and only if $κ$ is Ulam measurable, and there is a singular ${<}\,κ$-additive pure state on $B(l^2(κ))$ if and only if $κ$ is measurable. The proofs make use of Farah and Weaver's theory of quantum filters. Applications to Ueda's peak set theorem for von Neumann algebras are discussed in the final section. △ Less

Submitted 3 December, 2016; v1 submitted 28 July, 2016; originally announced July 2016.

Comments: 18 pages; added a section on general von Neumann algebras, plus some other minor improvements

MSC Class: 46L10; 46L30; 03E55; 03E75

A Multi-perspective Analysis of Carrier-Grade NAT Deployment

Authors: Philipp Richter, Florian Wohlfart, Narseo Vallina-Rodriguez, Mark Allman, Randy Bush, Anja Feldmann, Christian Kreibich, Nicholas Weaver, Vern Paxson

Abstract: As ISPs face IPv4 address scarcity they increasingly turn to network address translation (NAT) to accommodate the address needs of their customers. Recently, ISPs have moved beyond employing NATs only directly at individual customers and instead begun deploying Carrier-Grade NATs (CGNs) to apply address translation to many independent and disparate endpoints spanning physical locations, a phenomen… ▽ More As ISPs face IPv4 address scarcity they increasingly turn to network address translation (NAT) to accommodate the address needs of their customers. Recently, ISPs have moved beyond employing NATs only directly at individual customers and instead begun deploying Carrier-Grade NATs (CGNs) to apply address translation to many independent and disparate endpoints spanning physical locations, a phenomenon that so far has received little in the way of empirical assessment. In this work we present a broad and systematic study of the deployment and behavior of these middleboxes. We develop a methodology to detect the existence of hosts behind CGNs by extracting non-routable IP addresses from peer lists we obtain by crawling the BitTorrent DHT. We complement this approach with improvements to our Netalyzr troubleshooting service, enabling us to determine a range of indicators of CGN presence as well as detailed insights into key properties of CGNs. Combining the two data sources we illustrate the scope of CGN deployment on today's Internet, and report on characteristics of commonly deployed CGNs and their effect on end users. △ Less

Submitted 13 September, 2016; v1 submitted 18 May, 2016; originally announced May 2016.

Journal ref: Proceedings of ACM IMC 2016

A "quantum" Ramsey theorem for operator systems

Authors: Nik Weaver

Abstract: Let V be a linear subspace of M_n(C) which contains the identity matrix and is stable under the formation of Hermitian adjoints. We prove that if n is sufficiently large then there exists a rank k orthogonal projection P such that dim(PVP) = 1 or k^2. Let V be a linear subspace of M_n(C) which contains the identity matrix and is stable under the formation of Hermitian adjoints. We prove that if n is sufficiently large then there exists a rank k orthogonal projection P such that dim(PVP) = 1 or k^2. △ Less

Submitted 13 January, 2016; v1 submitted 3 January, 2016; originally announced January 2016.

Comments: 11 pages; added a final section which includes a common generalization of the classical and quantum Ramsey theorems

The Case for a General and Interaction-based Third-party Cookie Policy

Authors: Istemi Ekin Akkus, Nicholas Weaver

Abstract: The privacy implications of third-party tracking is a well-studied problem. Recent research has shown that besides data aggregators and behavioral advertisers, online social networks also act as trackers via social widgets. Existing cookie policies are not enough to solve these problems, pushing users to employ blacklist-based browser extensions to prevent such tracking. Unfortunately, such approa… ▽ More The privacy implications of third-party tracking is a well-studied problem. Recent research has shown that besides data aggregators and behavioral advertisers, online social networks also act as trackers via social widgets. Existing cookie policies are not enough to solve these problems, pushing users to employ blacklist-based browser extensions to prevent such tracking. Unfortunately, such approaches require maintaining and distributing blacklists, which are often too general and adversely affect non-tracking services for advertisements and analytics. In this paper, we propose and advocate for a general third-party cookie policy that prevents third-party tracking with cookies and preserves the functionality of social widgets without requiring a blacklist and adversely affecting non-tracking services. We implemented a proof-of-concept of our policy as browser extensions for Mozilla Firefox and Google Chrome. To date, our extensions have been downloaded about 11.8K times and have over 2.8K daily users combined. △ Less

Submitted 12 June, 2015; originally announced June 2015.

Comments: In Proceedings of the 9th Workshop on Web 2.0 Security and Privacy (W2SP) 2015

Quantum graphs as quantum relations

Authors: Nik Weaver

Abstract: The "noncommutative graphs" which arise in quantum error correction are a special case of the quantum relations introduced in [N. Weaver, Quantum relations, Mem. Amer. Math. Soc. 215 (2012), v-vi, 81-140]. We use this perspective to interpret the Knill-Laflamme error-correction conditions [E. Knill and R. Laflamme, Theory of quantum error-correcting codes, Phys. Rev. A 55 (1997), 900-911] in terms… ▽ More The "noncommutative graphs" which arise in quantum error correction are a special case of the quantum relations introduced in [N. Weaver, Quantum relations, Mem. Amer. Math. Soc. 215 (2012), v-vi, 81-140]. We use this perspective to interpret the Knill-Laflamme error-correction conditions [E. Knill and R. Laflamme, Theory of quantum error-correcting codes, Phys. Rev. A 55 (1997), 900-911] in terms of graph-theoretic independence, to give intrinsic characterizations of Stahlke's noncommutative graph homomorphisms [D. Stahlke, Quantum source-channel coding and non-commutative graph theory, arXiv:1405.5254] and Duan, Severini, and Winter's noncommutative bipartite graphs [R. Duan, S. Severini, and A. Winter, Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovasz number, IEEE Trans. Inform. Theory 59 (2013), 1164-1174], and to realize the noncommutative confusability graph associated to a quantum channel as the pullback of a diagonal relation. Our framework includes as special cases not only purely classical and purely quantum information theory, but also the "mixed" setting which arises in quantum systems obeying superselection rules. Thus we are able to define noncommutative confusability graphs, give error correction conditions, and so on, for such systems. This could have practical value, as superselection constraints on information encoding can be physically realistic. △ Less

Submitted 28 June, 2017; v1 submitted 11 June, 2015; originally announced June 2015.

Comments: 19 pages; added an appendix on superselection rules, which explain the relevance to quantum error correction of the "mixed classical/quantum" setting handled in this paper (see 2nd paragraph of the new abstract)

Detecting Fourier subspaces

Authors: Charles A. Akemann, Nik Weaver

Abstract: Let G be a finite abelian group. We examine the discrepancy between subspaces of l^2(G) which are diagonalized in the standard basis and subspaces which are diagonalized in the dual Fourier basis. The general principle is that a Fourier subspace whose dimension is small compared to |G| = dim(l^2(G)) tends to be far away from standard subspaces. In particular, the recent positive solution of the Ka… ▽ More Let G be a finite abelian group. We examine the discrepancy between subspaces of l^2(G) which are diagonalized in the standard basis and subspaces which are diagonalized in the dual Fourier basis. The general principle is that a Fourier subspace whose dimension is small compared to |G| = dim(l^2(G)) tends to be far away from standard subspaces. In particular, the recent positive solution of the Kadison-Singer problem shows that from within any Fourier subspace whose dimension is small compared to |G| there is standard subspace which is essentially indistinguishable from its orthogonal complement. △ Less

Submitted 23 March, 2015; originally announced March 2015.

Comments: 8 pages

MSC Class: 43A25; 94A12; 05A99; 11K38; 46L05

A Simple Quantum Integro-Differential Solver (SQuIDS)

Authors: Carlos Alberto Arguelles Delgado, Jordi Salvado, Christopher N. Weaver

Abstract: Simple Quantum Integro-Differential Solver (SQuIDS) is a C++ code designed to solve semi-analytically the evolution of a set of density matrices and scalar functions. This is done efficiently by expressing all operators in an SU(N) basis. SQuIDS provides a base class from which users can derive new classes to include new non-trivial terms from the right hand sides of density matrix equations. The… ▽ More Simple Quantum Integro-Differential Solver (SQuIDS) is a C++ code designed to solve semi-analytically the evolution of a set of density matrices and scalar functions. This is done efficiently by expressing all operators in an SU(N) basis. SQuIDS provides a base class from which users can derive new classes to include new non-trivial terms from the right hand sides of density matrix equations. The code was designed in the context of solving neutrino oscillation problems, but can be applied to any problem that involves solving the quantum evolution of a collection of particles with Hilbert space of dimension up to six. △ Less

Submitted 11 December, 2014; originally announced December 2014.

Comments: 36 pages, 4 figures. Code available at https://github.com/jsalvado/SQuIDS

Paradoxes of rational agency and formal systems that verify their own soundness

Authors: Nik Weaver

Abstract: We consider extensions of Peano arithmetic which include an assertibility predicate. Any such system which is arithmetically sound effectively verifies its own soundness. This leads to the resolution of a range of paradoxes involving rational agents who are licensed to act under precisely defined conditions. We consider extensions of Peano arithmetic which include an assertibility predicate. Any such system which is arithmetically sound effectively verifies its own soundness. This leads to the resolution of a range of paradoxes involving rational agents who are licensed to act under precisely defined conditions. △ Less

Submitted 21 December, 2013; v1 submitted 12 December, 2013; originally announced December 2013.

Comments: 10 pages

A Lyapunov type theorem from Kadison-Singer

Authors: Charles Akemann, Nik Weaver

Abstract: Marcus, Spielman, and Srivastava recently solved the Kadison-Singer problem by showing that if u_1, ..., u_m are column vectors in C^d such that \sum u_iu_i^* = I, then a set of indices S \subseteq {1, ..., m} can be chosen so that \sum_{i \in S} u_iu_i^* is approximately (1/2)I, with the approximation good in operator norm to order ε^{1/2} where ε= \max \|u_i\|^2. We extend their result to show t… ▽ More Marcus, Spielman, and Srivastava recently solved the Kadison-Singer problem by showing that if u_1, ..., u_m are column vectors in C^d such that \sum u_iu_i^* = I, then a set of indices S \subseteq {1, ..., m} can be chosen so that \sum_{i \in S} u_iu_i^* is approximately (1/2)I, with the approximation good in operator norm to order ε^{1/2} where ε= \max \|u_i\|^2. We extend their result to show that every linear combination of the matrices u_iu_i^* with coefficients in [0,1] can be approximated in operator norm to order ε^{1/8} by a matrix of the form \sum_{i \in S} u_iu_i^*. △ Less

Submitted 23 August, 2013; originally announced August 2013.

Comments: 9 pages

MSC Class: Primary 05A99; 11K38; 46L05

The Kadison-Singer problem in discrepancy theory, II

Authors: Nik Weaver

Abstract: We apply Srivastava's spectral sparsification technique to a vector balancing version of the Kadison-Singer problem. The result is a one-sided version of the conjectured solution. We apply Srivastava's spectral sparsification technique to a vector balancing version of the Kadison-Singer problem. The result is a one-sided version of the conjectured solution. △ Less

Submitted 10 March, 2013; originally announced March 2013.

Comments: 7 pages

MSC Class: 05A99; 11K38; 46L05

Reasoning about constructive concepts

Authors: Nik Weaver

Abstract: We find that second order quantification is problematic when a quantified concept variable is supposed to function predicatively. This issue is analyzed and it is shown that a constructive interpretation of the falling under relation suffices to resolve the difficulty. We are then able to present a formal system for reasoning about concepts. We prove that this system is consistent and we investiga… ▽ More We find that second order quantification is problematic when a quantified concept variable is supposed to function predicatively. This issue is analyzed and it is shown that a constructive interpretation of the falling under relation suffices to resolve the difficulty. We are then able to present a formal system for reasoning about concepts. We prove that this system is consistent and we investigate the extent to which it is able to interpret set theoretic and number theoretic systems of a more standard type. △ Less

Submitted 12 December, 2013; v1 submitted 28 December, 2011; originally announced December 2011.

Comments: corrected the existential quantification box law

Truth and the liar paradox

Authors: Nik Weaver

Abstract: We analyze the informal notion of truth and conclude that it can be formalized in essentially two distinct ways: constructively, in terms of provability, or classically, as a hierarchy of concepts which satisfy Tarski's biconditional in limited settings. This leads to a complete resolution of the liar paradox. We analyze the informal notion of truth and conclude that it can be formalized in essentially two distinct ways: constructively, in terms of provability, or classically, as a hierarchy of concepts which satisfy Tarski's biconditional in limited settings. This leads to a complete resolution of the liar paradox. △ Less

Submitted 28 December, 2011; originally announced December 2011.

Comments: 10 pages

The semantic conception of proof

Authors: Nik Weaver

Abstract: We analyze the informal semantic conception of proof and axiomatize the proof relation and the provability operator. A self referential propositional calculus which admits provable liar type sentences is introduced and proven consistent. We also investigate the problem of interpreting arbitrary formal systems in systems which include a provability operator. We analyze the informal semantic conception of proof and axiomatize the proof relation and the provability operator. A self referential propositional calculus which admits provable liar type sentences is introduced and proven consistent. We also investigate the problem of interpreting arbitrary formal systems in systems which include a provability operator. △ Less

Submitted 12 December, 2013; v1 submitted 28 December, 2011; originally announced December 2011.

Comments: reworked the treatment of quantification

Kinds of concepts

Authors: Nik Weaver

Abstract: The central focus is on clarifying the distinction between sets and proper classes. To this end we identify several categories of concepts (surveyable, definite, indefinite), and we attribute the classical set theoretic paradoxes to a failure to appreciate the distinction between surveyability and definiteness. The central focus is on clarifying the distinction between sets and proper classes. To this end we identify several categories of concepts (surveyable, definite, indefinite), and we attribute the classical set theoretic paradoxes to a failure to appreciate the distinction between surveyability and definiteness. △ Less

Submitted 28 December, 2011; originally announced December 2011.

Comments: 11 pages

Quantum relations

Authors: Nik Weaver

Abstract: We define a "quantum relation" on a von Neumann algebra M \subset B(H) to be a weak* closed operator bimodule over its commutant M'. Although this definition is framed in terms of a particular representation of M, it is effectively representation independent. Quantum relations on l^\infty(X) exactly correspond to subsets of X^2, i.e., relations on X. There is also a good definition of a "measurab… ▽ More We define a "quantum relation" on a von Neumann algebra M \subset B(H) to be a weak* closed operator bimodule over its commutant M'. Although this definition is framed in terms of a particular representation of M, it is effectively representation independent. Quantum relations on l^\infty(X) exactly correspond to subsets of X^2, i.e., relations on X. There is also a good definition of a "measurable relation" on a measure space, to which quantum relations partially reduce in the general abelian case. By analogy with the classical setting, we can identify structures such as quantum equivalence relations, quantum partial orders, and quantum graphs, and we can generalize Arveson's fundamental work on weak* closed operator algebras containing a masa to these cases. We are also able to intrinsically characterize the quantum relations on M in terms of families of projections in M \otimes B(l^2). △ Less

Submitted 3 May, 2010; originally announced May 2010.

Comments: 48 pages

A von Neumann algebra approach to quantum metrics

Authors: Greg Kuperberg, Nik Weaver

Abstract: We propose a new definition of quantum metric spaces, or W*-metric spaces, in the setting of von Neumann algebras. Our definition effectively reduces to the classical notion in the atomic abelian case, has both concrete and intrinsic characterizations, and admits a wide variety of tractable examples. A natural application and motivation of our theory is a mutual generalization of the standard mode… ▽ More We propose a new definition of quantum metric spaces, or W*-metric spaces, in the setting of von Neumann algebras. Our definition effectively reduces to the classical notion in the atomic abelian case, has both concrete and intrinsic characterizations, and admits a wide variety of tractable examples. A natural application and motivation of our theory is a mutual generalization of the standard models of classical and quantum error correction. △ Less

Submitted 29 September, 2010; v1 submitted 3 May, 2010; originally announced May 2010.

Comments: 68 pages; minor revisions

Intuitionism and the liar paradox

Authors: Nik Weaver

Abstract: The concept of informal mathematical proof considered in intuitionism is apparently vulnerable to a version of the liar paradox. However, a careful reevaluation of this concept reveals a subtle error whose correction blocks the contradiction. This leads to a general resolution of the classical semantic paradoxes. This paper is an expanded version of parts of my earlier paper "Constructive truth an… ▽ More The concept of informal mathematical proof considered in intuitionism is apparently vulnerable to a version of the liar paradox. However, a careful reevaluation of this concept reveals a subtle error whose correction blocks the contradiction. This leads to a general resolution of the classical semantic paradoxes. This paper is an expanded version of parts of my earlier paper "Constructive truth and circularity" [arXiv:0905.1681]. △ Less

Submitted 13 April, 2010; originally announced April 2010.

Comments: 13 pages

Periodic 2-graphs arising from subshifts

Authors: David Pask, Iain Raeburn, Natasha Weaver

Abstract: Higher-rank graphs were introduced by Kumjian and Pask to provide models for higher-rank Cuntz-Krieger algebras. In a previous paper, we constructed 2-graphs whose path spaces are rank-two subshifts of finite type, and showed that this construction yields aperiodic 2-graphs whose $C^*$-algebras are simple and are not ordinary graph algebras. Here we show that the construction also gives a family… ▽ More Higher-rank graphs were introduced by Kumjian and Pask to provide models for higher-rank Cuntz-Krieger algebras. In a previous paper, we constructed 2-graphs whose path spaces are rank-two subshifts of finite type, and showed that this construction yields aperiodic 2-graphs whose $C^*$-algebras are simple and are not ordinary graph algebras. Here we show that the construction also gives a family of periodic 2-graphs which we call \emph{domino graphs}. We investigate the combinatorial structure of domino graphs, finding interesting points of contact with the existing combinatorial literature, and prove a structure theorem for the $C^*$-algebras of domino graphs. △ Less

Submitted 3 November, 2009; originally announced November 2009.

Comments: 17 pages

MSC Class: 46L05; 37B10

Constructive truth and circularity

Authors: Nik Weaver

Abstract: We propose a constructive interpretation of truth which resolves the standard semantic paradoxes. We propose a constructive interpretation of truth which resolves the standard semantic paradoxes. △ Less

Submitted 13 April, 2010; v1 submitted 11 May, 2009; originally announced May 2009.

Comments: corrected the discussion of Berry's paradox on page 8

Is set theory indispensable?

Authors: Nik Weaver

Abstract: Although Zermelo-Fraenkel set theory (ZFC) is generally accepted as the appropriate foundation for modern mathematics, proof theorists have known for decades that virtually all mainstream mathematics can actually be formalized in much weaker systems which are essentially number-theoretic in nature. Feferman has observed that this severely undercuts a famous argument of Quine and Putnam according… ▽ More Although Zermelo-Fraenkel set theory (ZFC) is generally accepted as the appropriate foundation for modern mathematics, proof theorists have known for decades that virtually all mainstream mathematics can actually be formalized in much weaker systems which are essentially number-theoretic in nature. Feferman has observed that this severely undercuts a famous argument of Quine and Putnam according to which set theoretic platonism is validated by the fact that mathematics is "indispensable" for some successful scientific theories (since in fact ZFC is not needed for the mathematics that is currently used in science). I extend this critique in three ways: (1) not only is it possible to formalize core mathematics in these weaker systems, they are in important ways better suited to the task than ZFC; (2) an improved analysis of the proof-theoretic strength of predicative theories shows that most if not all of the already rare examples of mainstream theorems whose proofs are currently thought to require metaphysically substantial set-theoretic principles actually do not; and (3) set theory itself, as it is actually practiced, is best understood in formalist, not platonic, terms, so that in a real sense *set theory is not even indispensable for set theory*. I also make the point that even if ZFC is consistent, there are good reasons to suspect that some number-theoretic assertions provable in ZFC may be false. This suggests that set theory should not be considered central to mathematics. △ Less

Submitted 11 May, 2009; originally announced May 2009.

Comments: 21 pages

The concept of a set

Authors: Nik Weaver

Abstract: Metaphysical interpretations of set theory are either inconsistent or incoherent. The uses of sets in mathematics actually involve three distinct kinds of collections (surveyable, definite, and heuristic), which are governed by three different kinds of logic (classical, intuitionistic, and minimal). A foundational system incorporating this analysis and based on the principles of mathematical con… ▽ More Metaphysical interpretations of set theory are either inconsistent or incoherent. The uses of sets in mathematics actually involve three distinct kinds of collections (surveyable, definite, and heuristic), which are governed by three different kinds of logic (classical, intuitionistic, and minimal). A foundational system incorporating this analysis and based on the principles of mathematical conceptualism accords better with actual mathematical practice than Zermelo-Fraenkel set theory does. △ Less

Submitted 11 May, 2009; originally announced May 2009.

Comments: 11 pages

Axiomatizing mathematical conceptualism in third order arithmetic

Authors: Nik Weaver

Abstract: We review the philosophical framework of mathematical conceptualism as an alternative to set-theoretic foundations and show how mainstream mathematics can be developed on this basis. The paper includes an explicit axiomatization of the basic principles of conceptualism in a formal system CM set in the language of third order arithmetic. We review the philosophical framework of mathematical conceptualism as an alternative to set-theoretic foundations and show how mainstream mathematics can be developed on this basis. The paper includes an explicit axiomatization of the basic principles of conceptualism in a formal system CM set in the language of third order arithmetic. △ Less

Submitted 11 May, 2009; originally announced May 2009.

Comments: 31 pages

A family of 2-graphs arising from two-dimensional subshifts

Authors: David Pask, Iain Raeburn, Natasha A. Weaver

Abstract: Higher-rank graphs (or $k$-graphs) were introduced by Kumjian and Pask to provide combinatorial models for the higher-rank Cuntz-Krieger $C^*$-algebras of Robertson and Steger. Here we consider a family of finite 2-graphs whose path spaces are dynamical systems of algebraic origin, as studied by Schmidt and others. We analyse the $C^*$-algebras of these 2-graphs, find criteria under which they a… ▽ More Higher-rank graphs (or $k$-graphs) were introduced by Kumjian and Pask to provide combinatorial models for the higher-rank Cuntz-Krieger $C^*$-algebras of Robertson and Steger. Here we consider a family of finite 2-graphs whose path spaces are dynamical systems of algebraic origin, as studied by Schmidt and others. We analyse the $C^*$-algebras of these 2-graphs, find criteria under which they are simple and purely infinite, and compute their $K$-theory. We find examples whose $C^*$-algebras satisfy the hypotheses of the classification theorem of Kirchberg and Phillips, but are not isomorphic to the $C^*$-algebras of ordinary directed graphs. △ Less

Submitted 22 April, 2008; originally announced April 2008.

Comments: 28 pages, 3 figures, 1 table

MSC Class: 46L05; 37B50

Pure states on free group C*-algebras

Authors: Charles Akemann, Simon Wassermann, Nik Weaver

Abstract: We prove that all of the pure states of the reduced C*-algebra of the free goup on $\aleph_1$ generators are *-automorphism equivalent and extract some consequences of that fact. We prove that all of the pure states of the reduced C*-algebra of the free goup on $\aleph_1$ generators are *-automorphism equivalent and extract some consequences of that fact. △ Less

Submitted 6 November, 2007; v1 submitted 8 May, 2007; originally announced May 2007.

Comments: 3 pages, results improved with the addition of a third author

Classically normal pure states

Authors: Charles Akemann, Nik Weaver

Abstract: A pure state f of a von Neumann algebra M is called classically normal if f is normal on any von Neumann subalgebra of M on which f is multiplicative. Assuming the continuum hypothesis, a separably represented von Neumann algebra M has classically normal, singular pure states iff there is a central projection p in M such that Mp is a factor of type I_\infty, II, or III. A pure state f of a von Neumann algebra M is called classically normal if f is normal on any von Neumann subalgebra of M on which f is multiplicative. Assuming the continuum hypothesis, a separably represented von Neumann algebra M has classically normal, singular pure states iff there is a central projection p in M such that Mp is a factor of type I_\infty, II, or III. △ Less

Submitted 7 May, 2007; originally announced May 2007.

MSC Class: 46L10

The Calkin algebra has outer automorphisms

Authors: N. Christopher Phillips, Nik Weaver

Abstract: Assuming the continuum hypothesis, we show that the Calkin algebra has 2^{aleph_1} outer automorphisms. Assuming the continuum hypothesis, we show that the Calkin algebra has 2^{aleph_1} outer automorphisms. △ Less

Submitted 23 June, 2006; originally announced June 2006.

Comments: 13 pages

MSC Class: 46L40; 46L05; 03E50

Not all pure states on B(H) are diagonalizable

Authors: Charles Akemann, Nik Weaver

Abstract: Assuming the continuum hypothesis, we prove that B(H) has a pure state whose restriction to any masa is not pure. This resolves negatively an old conjecture of Anderson. Assuming the continuum hypothesis, we prove that B(H) has a pure state whose restriction to any masa is not pure. This resolves negatively an old conjecture of Anderson. △ Less

Submitted 7 June, 2006; originally announced June 2006.

Comments: 3 pages

MSC Class: 46A32; 46L30; 47L05 ; 03E50

Set theory and C*-algebras

Authors: Nik Weaver

Abstract: We survey the use of extra-set-theoretic hypotheses, mainly the continuum hypothesis, in the C*-algebra literature. The Calkin algebra emerges as a basic object of interest. We survey the use of extra-set-theoretic hypotheses, mainly the continuum hypothesis, in the C*-algebra literature. The Calkin algebra emerges as a basic object of interest. △ Less

Submitted 9 April, 2006; originally announced April 2006.

Comments: 16 pages; to appear in Bull. Symb. Logic

MSC Class: 03E35; 03E50; 03E75; 46L05; 46L85

Mathematical conceptualism

Authors: Nik Weaver

Abstract: This is an explanation and defense of "mathematical conceptualism" for a general mathematical and philosophical audience. I make a case that it is cogent, rigorous, attractive, and better suited to ordinary mathematical practice than all other foundational stances. This is an explanation and defense of "mathematical conceptualism" for a general mathematical and philosophical audience. I make a case that it is cogent, rigorous, attractive, and better suited to ordinary mathematical practice than all other foundational stances. △ Less

Submitted 12 September, 2005; v1 submitted 11 September, 2005; originally announced September 2005.

Comments: 18 pages

Analysis in J_2

Authors: Nik Weaver

Abstract: This is an expository paper in which I explain how core mathematics, particularly abstract analysis, can be developed within a concrete countable set J_2 (the second set in Jensen's constructible hierarchy). The implication, well-known to proof theorists but probably not to most mainstream mathematicians, is that ordinary mathematical practice does not require an enigmatic metaphysical universe… ▽ More This is an expository paper in which I explain how core mathematics, particularly abstract analysis, can be developed within a concrete countable set J_2 (the second set in Jensen's constructible hierarchy). The implication, well-known to proof theorists but probably not to most mainstream mathematicians, is that ordinary mathematical practice does not require an enigmatic metaphysical universe of sets. I go further and argue that J_2 is a superior setting for normal mathematics because it is free of irrelevant set-theoretic pathologies and permits stronger formulations of existence results. △ Less

Submitted 12 September, 2005; v1 submitted 11 September, 2005; originally announced September 2005.

Comments: 31 pages

Predicativity beyond Gamma_0

Authors: Nik Weaver

Abstract: We reevaluate the claim that predicative reasoning (given the natural numbers) is limited by the Feferman-Schutte ordinal Gamma_0. First we comprehensively criticize the arguments that have been offered in support of this position. Then we analyze predicativism from first principles and develop a general method for accessing ordinals which is predicatively valid according to this analysis. We fi… ▽ More We reevaluate the claim that predicative reasoning (given the natural numbers) is limited by the Feferman-Schutte ordinal Gamma_0. First we comprehensively criticize the arguments that have been offered in support of this position. Then we analyze predicativism from first principles and develop a general method for accessing ordinals which is predicatively valid according to this analysis. We find that the Veblen ordinal φ_{Ω^ω}(0), and larger ordinals, are predicatively provable. △ Less

Submitted 11 May, 2009; v1 submitted 11 September, 2005; originally announced September 2005.

Comments: 38 pages Some minor corrections; no major changes

Consistency of a counterexample to Naimark's problem

Authors: Charles Akemann, Nik Weaver

Abstract: We construct a C*-algebra that has only one irreducible representation up to unitary equivalence but is not isomorphic to the algebra of compact operators on any Hilbert space. This answers an old question of Naimark. Our construction uses a combinatorial statement called the diamond principle, which is known to be consistent with but not provable from the standard axioms of set theory (assuming… ▽ More We construct a C*-algebra that has only one irreducible representation up to unitary equivalence but is not isomorphic to the algebra of compact operators on any Hilbert space. This answers an old question of Naimark. Our construction uses a combinatorial statement called the diamond principle, which is known to be consistent with but not provable from the standard axioms of set theory (assuming those axioms are consistent). We prove that the statement ``there exists a counterexample to Naimark's problem which is generated by $\aleph_1$ elements'' is undecidable in standard set theory. △ Less

Submitted 5 December, 2003; originally announced December 2003.

Comments: 10 pages

Operator algebras associated with the Klein-Gordon position representation in relativistic quantum mechanics

Authors: Nik Weaver

Abstract: We initiate a mathematically rigorous study of Klein-Gordon position operators in single-particle relativistic quantum mechanics. Although not self-adjoint, these operators have real spectrum and enjoy a limited form of spectral decomposition. The associated C*-algebras are identifiable as crossed products. We also introduce a variety of non self-adjoint operator algebras associated with the Kle… ▽ More We initiate a mathematically rigorous study of Klein-Gordon position operators in single-particle relativistic quantum mechanics. Although not self-adjoint, these operators have real spectrum and enjoy a limited form of spectral decomposition. The associated C*-algebras are identifiable as crossed products. We also introduce a variety of non self-adjoint operator algebras associated with the Klein-Gordon position representation; these algebras are commutative and continuously (but not homeomorphically) embeddable in corresponding function algebras. Several open problems are indicated. △ Less

Submitted 7 September, 2002; originally announced September 2002.

Comments: 28 pages

MSC Class: 47L30; 47L15; 81R15; 47L90; 46L52; 46J99

The Kadison-Singer problem in discrepancy theory

Authors: Nik Weaver

Abstract: We give a combinatorial form of the Kadison-Singer problem, a famous problem in C*-algebra. This combinatorial problem, which has several minor variations, is a discrepancy question about vectors in C^n. Some partial results can be easily deduced from known facts in discrepancy theory. We give a combinatorial form of the Kadison-Singer problem, a famous problem in C*-algebra. This combinatorial problem, which has several minor variations, is a discrepancy question about vectors in C^n. Some partial results can be easily deduced from known facts in discrepancy theory. △ Less

Submitted 7 September, 2002; originally announced September 2002.

Comments: 13 pages

MSC Class: 05A99; 11K38; 46L05

Set theory and cyclic vectors

Authors: Nik Weaver

Abstract: Let H be a separable, infinite dimensional Hilbert space and let S be a countable subset of H. Then most positive operators on H have the property that every nonzero vector in the span of S is cyclic, in the sense that the set of operators in the positive part of the unit ball of B(H) with this property is comeager for the strong operator topology. Suppose κis a regular cardinal such that κ\ge… ▽ More Let H be a separable, infinite dimensional Hilbert space and let S be a countable subset of H. Then most positive operators on H have the property that every nonzero vector in the span of S is cyclic, in the sense that the set of operators in the positive part of the unit ball of B(H) with this property is comeager for the strong operator topology. Suppose κis a regular cardinal such that κ\geq ω_1 and 2^{<κ} = κ. Then it is relatively consistent with ZFC that 2^ω= κand for any subset S \subset H of cardinality less than κthe set of positive operators in the unit ball of B(H) for which every nonzero vector in the span of S is cyclic is comeager for the strong operator topology. △ Less

Submitted 25 February, 2002; originally announced February 2002.

Comments: 6 pages

MSC Class: 03E35; 03E50; 47A15; 47A16

A prime C*-algebra that is not primitive

Authors: Nik Weaver

Abstract: We construct a non-separable C*-algebra that is prime but not primitive. We construct a non-separable C*-algebra that is prime but not primitive. △ Less

Submitted 6 July, 2001; v1 submitted 28 June, 2001; originally announced June 2001.

Comments: 5 pages. The revised version of the paper gives a sharper version of the counterexample, in the sense that it is generated by a set of cardinality 2^{\aleph_0} rather than 2^{\aleph_1}. This allows for a less set-theoretically technical argument, although the proof of primality is slightly trickier

MSC Class: 46L05; 16G99

A counterexample to a conjecture of Akemann and Anderson

Authors: Nik Weaver

Abstract: Akemann and Anderson made a conjecture about ``paving'' projections in finite dimensional matrix algebras which, if true, would settle the well-known Kadison-Singer problem. We falsify their conjecture by an explicit seqence of counterexamples. Akemann and Anderson made a conjecture about ``paving'' projections in finite dimensional matrix algebras which, if true, would settle the well-known Kadison-Singer problem. We falsify their conjecture by an explicit seqence of counterexamples. △ Less

Submitted 22 May, 2001; originally announced May 2001.

Comments: 1 figure in a separate LaTex file

MSC Class: 46L30; 47A30; 15A60

Automatic convexity

Authors: Charles A. Akemann, Nik Weaver

Abstract: In many cases the convexity of the image of a linear map with range is $R^n$ is automatic because of the facial structure of the domain of the map. We develop a four step procedure for proving this kind of ``automatic convexity''. To make this procedure more efficient, we prove two new theorems that identify the facial structure of the intersection of a convex set with a subspace in terms of the… ▽ More In many cases the convexity of the image of a linear map with range is $R^n$ is automatic because of the facial structure of the domain of the map. We develop a four step procedure for proving this kind of ``automatic convexity''. To make this procedure more efficient, we prove two new theorems that identify the facial structure of the intersection of a convex set with a subspace in terms of the facial structure of the original set. Let $K$ be a convex set in a real linear space $X$ and let $H$ be a subspace of X that meets $K$. In Part I we show that the faces of $K\cap H$ have the form $F\cap H$ for a face $F$ of $K$. Then we extend our intersection theorem to the case where $X$ is a locally convex linear topological space, $K$ and $H$ are closed, and $H$ has finite codimension in $X$. In Part II we use our procedure to ``explain'' the convexity of the numerical range (and some of its generalizations) of a complex matrix. In Part III we use the topological version of our intersection theorem to prove a version of Lyapunov's theorem with finitely many linear constraints. We also extend Samet's continuous lifting theorem to the same constrained siuation. △ Less

Submitted 17 May, 2001; originally announced May 2001.

Comments: 10 pages

MSC Class: 46A55; 47A12; 46G10