An official website of the United States government
Dividing asks about inconsistency along indiscernible sequences. In order to study the finer structure of simple theories without much dividing, the authors recently introduced shearing, which essentially asks about inconsistency along generalized indiscernible sequences. Here we characterize the shearing of the random graph. We then use shearing to distinguish between the random graph and the theories $$T_{n,k}$$, the higher-order analogues of the triangle-free random graph. It follows that shearing is distinct from dividing in simple unstable theories, and distinguishes meaningfully between classes of simple unstable rank one theories. The paper begins with an overview of shearing, and includes open questions.
more »
« less
A separation theorem for simple theories
This paper builds model-theoretic tools to detect changes in complexity among the simple theories. We develop a generalization of dividing, called shearing, which depends on a so-called context c. This leads to defining c-superstability, a syntactical notion, which includes supersimplicity as a special case. The main result is a separation theorem showing that for any countable context and any two theories T1, T2, such that T1 is c-superstable and T2 is c-unsuperstable, and for arbitrarily large mu, it is possible to build models of any theory interpreting both T1 and T2 whose restriction to tau(T1) is mu-saturated and whose restriction to tau(T2) is not aleph1-saturated. (This suggests “c-superstable” is really a dividing line.) The proof uses generalized Ehrenfeucht-Mostowski models, and along the way, we clarify the use of these techniques to realize certain types while omitting others. In some sense, shearing allows us to study the interaction of complexity coming from the usual notion of dividing in simple theories and the more combinatorial complexity detected by the general definition. This work is inspired by our recent progress on Keisler’s order, but does not use ultrafilters, rather aiming to build up the internal model theory of these classes. https://doi.org/10.1090/tran/8513
more »
« less
- Award ID(s):
- 2051825
- PAR ID:
- 10423762
- Date Published:
- Journal Name:
- Transactions of the American Mathematical Society
- Volume:
- 375
- Issue:
- 2022
- ISSN:
- 0002-9947
- Page Range / eLocation ID:
- 1171-1205
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We develop the theory of Kim-independence in the context of NSOP $$_{1}$$ theories satisfying the existence axiom. We show that, in such theories, Kim-independence is transitive and that -Morley sequences witness Kim-dividing. As applications, we show that, under the assumption of existence, in a low NSOP $$_{1}$$ theory, Shelah strong types and Lascar strong types coincide and, additionally, we introduce a notion of rank for NSOP $$_{1}$$ theories.more » « less
-
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the t-disjoint-repair-group property than previously known constructions. More precisely, we show that, for t <=sqrt{N}, lifted multiplicity codes with length N and redundancy O(t^{0.585} sqrt{N}) have the property that any symbol of a codeword can be reconstructed in t different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant t < sqrt{N}. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.more » « less
-
null (Ed.)In the conventional robust T -colluding private information retrieval (PIR) system, the user needs to retrieve one of the possible messages while keeping the identity of the requested message private from any T colluding servers. Motivated by the possible heterogeneous privacy requirements for different messages, we consider the ( N,T1:K1,T2:K2 ) two-level PIR system, where K1 messages need to be retrieved privately against T1 colluding servers, and all the messages need to be retrieved privately against T2 colluding servers where T2≤T1 . We obtain a lower bound to the capacity by proposing a novel coding scheme, namely the non-uniform successive cancellation scheme. A capacity upper bound is also derived. The gap between the upper bound and the lower bound is analyzed, and shown to vanish when T1=T2 .more » « less
-
null (Ed.)The COVID-19 pandemic has caused financial stress and disrupted daily life more quickly than any prior economic downturn and on a scale beyond any prior natural disaster. This study aimed to assess the impact of the pandemic on psychological distress and identify vulnerable groups using longitudinal data to account for pre-pandemic mental health status. Clinically significant psychological distress was assessed with the Kessler-6 in a national probability sample of adults in the United States at two time points, February 2019 (T1) and May 2020 (T2). To identify increases in distress, psychological distress during the worst month of the past year at T1 was compared with psychological distress over the past 30-days at T2. Survey adjusted logistic regression was used to estimate associations of demographic characteristics at T1 (gender, age, race, and income) and census region at T2 with within-person increases in psychological distress. The past-month prevalence of serious psychological distress at T2 was as high as the past-year prevalence at T1 (10.9% vs. 10.2%). Psychological distress was strongly associated across assessments (X2(4) = 174.6, p < .0001). Increase in psychological distress above T1 was associated with gender, age, household income, and census region. Equal numbers of people experienced serious psychological distress in 30-days during the pandemic as did over an entire year prior to the pandemic. Mental health services and research efforts should be targeted to those with a history of mental health conditions and groups identified as at high risk for increases in distress above pre-pandemic levels.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/tran/8513
