text:
AGHmatrix: An R package to compute relationship matrices for diploid and autopolyploid species In AGHmatrix: Relationship Matrices for Diploid and Autopolyploid Species

library(knitr)
library(rmarkdown)

knitr::opts_chunkset(collapse = TRUE, comment = "#>", fig.width = 6, fig.height = 6, fig.align = "center", dev = "png", dpi = 36, cache = TRUE)  library(AGHmatrix)  Contact Rodrigo R Amadeu rramadeu at ufl dot edu Horticultural Sciences Department University of Florida https://rramadeu.github.io Overview AGHmatrix software is an R-package to build relationship matrices using pedigree (A matrix) and/or molecular markers (G matrix) with the possibility to build a combined matrix of Pedigree corrected by Molecular (H matrix). The package works with diploid and autopolyploid Data. If you are not familiar with R, we recommend the reading of vignette Introduction to R. Matrices computation implemented in the AGHmatrix Currently can compute the following 14 different relationship matrices: Pedigree-based relationship matrix (A matrix) | | Additive |Non-Additive | |---------------|---------------------------|-----------------| | Diploid | Henderson (1976) |Cockerham (1954) | | Polyploid |Kerr (2012), Slater (2013) | | Molecular-based relationship matrix (G matrix) | | Additive |Non-Additive | |---------------|---------------------------|-----------------| | Diploid | Yang (2010), VanRaden (2012) | Su (2012), Vitezica (2013) | | Polyploid | Slater (2016), VanRaden (2012) | Slater (2016), Endelman (2018) | Combined pedigree and molecular-based relationship matrix (H matrix) | Any ploidy/effect | |---------------------------| | Munoz (2014), Martini (2018) | Citation To cite this R package: Amadeu, R. R., C. Cellon, J. W. Olmstead, A. A. F. Garcia, M. F. R. Resende, and P. R. Munoz. 2016. AGHmatrix: R Package to Construct Relationship Matrices for Autotetraploid and Diploid Species: A Blueberry Example. The Plant Genome 9(3). doi: 10.3835/plantgenome2016.01.0009 Installing and loading Within R: ## Install stable version install.packages("AGHmatrix") ## Install development version #install.packages("devtools") #devtools::install_github("prmunoz/AGHmatrix") ## Load library(AGHmatrix)  Relationship matrices using pedigree data - A matrix Amatrix process the pedigree and build the A-matrix related to that given pedigree. The matrix is build according to the recursive method presented in Mrode (2014) and described by Henderson (1976). This method is expanded for higher ploidies (n-ploidy) according with Kerr et al. (2012). After loading the package you have to load your data file into the software. To do this, you can use the function read.data() or read.csv() for example. Your data should be available in R as a data.frame structure in the following order: column 1 must be the individual/genotype names (id), columns 2 and 3 must be the parent names. For the algorhitm does not matter who is the mom and who is the dad. In the package there is a pedigree data example (ped.mrode) that can be used to look at the structure and order the data. To load ped.mrode: data(ped.mrode) ped.mrode str(ped.mrode) #check the structure  The example ped.mrode has 3 columns, column 1 contains the names of the individual/genotypes, column 2 contains the names of the first parent, column 3 contains the names of the second parental. There is no header and the unknown value must be equal 0. Your data has to be in the same format of ped.mrode. Internally in the algorithm, the first step is the pre-processing of the pedigree: the individuals are numerated1$to$n$. Then, it is verified whether the genotypes in the pedigree are in chronological order (i.e. if the parents of a given individual are located prior to this individual in the pedigree dataset). If this order is not followed, the algorithm performs the necessary permutations to correct them. After this pre-processing, the matrices computation proceeds as in Mrode (2014) for diploid - for additive or dominance relationship - and as in Kerr et al. (2012) for autotetraploids - for additive relationship. For autotetraploids there is the option to include double-reduction fraction (as presented Slater et al., 2014). For diploids there is the option to compute the non-additive relationship matrix (Cockerham, 1954). It follows some usage examples with the ped.mrode. #Computing additive relationship matrix for diploids: Amatrix(ped.mrode, ploidy=2) #Computing non-additive relationship matrix considering diploidy: Amatrix(ped.mrode, ploidy=2, dominance=TRUE) #Computing additive relationship matrix considering autotetraploidy: Amatrix(ped.mrode, ploidy=4) #Computing additive relationship matrix considering autooctaploidy: Amatrix(ped.mrode, ploidy=8) #Computing additive relationship matrix considering autotetraploidy # and double-reduction of 10%: Amatrix(ped.mrode, ploidy=4, w=0.1) #Computing additive relationship matrix considering autotetraploidy # and double-reduction of 10% as Slater et al. (2014): Amatrix(ped.mrode, ploidy=4, w=0.1, slater = TRUE) #Computing additive relationship matrix considering autohexaploidy # and double-reduction of 10%: Amatrix(ped.mrode, ploidy=6, w=0.1)  More information about Amatrix can be found with: ?Amatrix  Relationship matrices using the molecular data - G matrix for diploids Gmatrix handles the molecular-markers matrix and builds the relationship matrix. Molecular markers data should be organized in a matrix format (individuals in rows and markers in columns) coded as 0,1,2 and missing data value (numeric or NA). Import your molecular marker data into R with the function read.table() or read.csv() and convert to a matrix format with the function as.matrix(). The function Gmatrix can be used to construct the additive relationship either as proposed by Yang et al. (2010) or the proposed by VanRaden (2008). The function can also construct the dominance relationship matrix either as proposed by Su et al. (2012) or as proposed by Vitezica et al. (2013). As an example, here we build the four matrices using real data from Resende et al. (2012). To load snp.pine and to check its structure: data(snp.pine) snp.pine[1:5,1:5] str(snp.pine)  In this dataset we have 926 individuals with 4853 markers and the missing data value is -9. It follows some usage examples with the snp.pine data where the unknown value (missingValue) is -9. Here we set minimum allele frequency to 0.05. #Computing the additive relationship matrix based on VanRaden 2008 G_VanRadenPine <- Gmatrix(SNPmatrix=snp.pine, missingValue=-9, maf=0.05, method="VanRaden") #Computing the additive relationship matrix based on Yang 2010 G_YangPine <- Gmatrix(SNPmatrix=snp.pine, missingValue=-9, maf=0.05, method="Yang") #Computing the dominance relationship matrix based on Su 2012 G_SuPine <- Gmatrix(SNPmatrix=snp.pine, missingValue=-9, maf=0.05, method="Su") #Computing the dominance relationship matrix based on Vitezica 2013 G_VitezicaPine <- Gmatrix(SNPmatrix=snp.pine, missingValue=-9, maf=0.05, method="Vitezica")  More information about Gmatrix can be found with: ?Gmatrix  Relationship matrices using the molecular data - G matrix for autopolyploids Molecular markers data should be organized in a matrix format (individual in rows and markers in columns) coded according to the dosage level: 0,1,2,...,ploidy level, and missing data value (numeric or NA). As an example, an autotetraploid should be coded as 0,1,2,3,4, and missing data value. In autopolyploids, the function Gmatrix can be used to construct: i) the additive relationship based on VanRaden (2008) and extended by Ashraf (2016); ii) the full-autopolyploid including additive and non-additive model as equations 8 and 9 in Slater et al. (2016); iii) the pseudo-diploid model as equations 5, 6, and 7 Slater et al. (2016). iv) the digenic-dominant model based on Endelman et al. (2018). As an example, here we build the matrices using data from Endelman et al. (2018) (snp.sol). #Loading the data data(snp.sol) str(snp.sol) #Computing the additive relationship matrix based on VanRaden 2008 # adapted by Ashraf 2016 G_VanRaden <- Gmatrix(snp.sol, method="VanRaden", ploidy=4) #Computing the dominance (digenic) matrix based on Endelman 2018 (Eq. 19) G_Dominance <- Gmatrix(snp.sol, method="Endelman", ploidy=4) #Computing the full-autopolyploid matrix based on Slater 2016 (Eq. 8 # and 9) G_FullAutopolyploid <- Gmatrix(snp.sol, method="Slater", ploidy=4) #Computing the pseudodiploid matrix based on Slater 2016 (Eq. 5, 6, # and 7) G_Pseudodiploid <- Gmatrix(snp.sol, method="VanRaden", ploidy=4, pseudo.diploid=TRUE)  More information about Gmatrix can be found with: ?Gmatrix  Combined relationship matrix - H matrix H matrix is the relationship matrix using combined information from the pedigree and genomic relationship matrices. First, you need to compute the matrices separated and then use them as input to build the combined H matrix. Two methods are implemented. Munoz shirinks the G matrix towards the A matrix scaling the molecular relatadness by each relationship classes. Martini is a modified version from Legarra et al. 2009 where combines A and G matrix using scaling factors. As an example, here we build the matrices using data from Endelman et al. (2018) (ped.sol and snp.sol). data(ped.sol) data(snp.sol) #Computing the numerator relationship matrix 10% of double-reduction Amat <- Amatrix(ped.sol, ploidy=4, w = 0.1) #Computing the additive relationship matrix based on VanRaden (modified) Gmat <- Gmatrix(snp.sol, ploidy=4, missingValue=-9, maf=0.05, method="VanRaden") #Computing H matrix (Martini) Hmat_Martini <- Hmatrix(A=Amat, G=Gmat, method="Martini", ploidy=4, missingValue=-9, maf=0.05) #Computing H matrix (Munoz) Hmat_Munoz <- Hmatrix(A=Amat, G=Gmat, markers = snp.sol, ploidy=4, method="Munoz", missingValue=-9, maf=0.05)  Covariance matrices due to epistatic terms Here we present how to compute the epistasis relationship matrices using Hadamard products (i.e. cell-by-cell product), denoted by *. For more information please see Munoz et al. (2014). In this example we are using the molecular-based relationship matrices. First, build the additive and dominance matrices: data(snp.pine) A <- Gmatrix(SNPmatrix=snp.pine, method="VanRaden", missingValue=-9, maf=0.05) D <- Gmatrix(SNPmatrix=snp.pine, method="Vitezica", missingValue=-9,maf=0.05)  For the first degree epistatic terms: #Additive-by-Additive Interactions A_A <- A*A #Dominance-by-Additive Interactions D_A <- D*A #Dominance-by-Dominance Interactions D_D <- D*D  For the second degree epistatic terms: #Additive-by-Additive-by-Additive Interactions A_A_A <- A*A*A #Additive-by-Additive-by-Dominance Interactions A_A_D <- A*A*D #Additive-by-Dominance-by-Dominance Interactions A_D_D <- A*D*D #Dominance-by-Dominance-by-Dominance Interactions D_D_D <- D*D*D  And so on... Exporting your matrix as three columns and sparse format (ASReml - csv format) That is the lower diagonal matrix formatted in three columns in .csv format (other ASCII extension could be used as well). In order to do this, we need to build a matrix, its inverse, and export it using formatmatrix function. ASReml can invert the relationship matrix as well, probably more efficiently than R for large matrices (i.e. solve() function), so no need to invert the matrix in R if matrix is large. This function has as options: round.by, which let you decide the number of decimals you want; exclude.0, if TRUE, remove all the zeros from your data (i.e., transforms into sparse); and, name that defines the name to be used in the exported file. Use the default if not sure what parameter use in these function. Here an example using ped.mrode data: #Loading the data example data(ped.mrode) #Computing the matrix A <- Amatrix(data=ped.mrode, ploidy=4, w=0.1) #Building its inverse Ainv <- solve(A) #Exporting it. The function "formatmatrix" # will convert it and save in your working directory formatmatrix(Ainv, round.by=12, exclude.0=TRUE, name="Ainv")  Bibliography Amadeu, RR, et al., 2016 AGHmatrix: R package to construct relationship matrices for autotetraploid and diploid species: a blueberry example. The Plant Genome 9(4). https://doi.org/10.3835/plantgenome2016.01.0009 Ashraf, BH, et a., 2016 Estimating genomic heritabilities at the level of family-pool samples of perennial ryegrass using genotyping-by-sequencing. Theoretical and Applied Genetics 129: 45-52. https://doi.org/0.1007/s00122-015-2607-9 Endelman, JB, et al., 2018. Genetic variance partitioning and genome-wide prediction with allele dosage information in autotetraploid potato. Genetics, 209(1) pp. 77-87. https://doi.org/10.1534/genetics.118.300685 Hamilton, MG, et al., 2017 Computation of the inverse additive relationship matrix for autopolyploid and multiple-ploidy populations. Theoretical and Applied Genetics. https://doi.org/10.1007/s00122-017-3041-y Henderson, C, 1976 A simple method for computing the inverse of a numerator relationship matrix used in prediction of breeding values. Biometrics pp. 69–83. https://doi.org/10.2307/2529339 Kerr, RJ, et al., 2012 Use of the numerator relation ship matrix in genetic analysis of autopolyploid species. Theoretical and Applied Genetics 124: 1271–1282. https://doi.org/10.1007/s00122-012-1785-y Martini, JW, et al., 2018, The effect of the H$^{1}$scaling factors$\tau$and$\omega\$ on the structure of H in the single-step procedure. Genetics Selection Evolution, 50(1), 16. https://doi.org/10.1186/s12711-018-0386-x

Mrode, R. A., 2014 Linear models for the prediction of animal breeding values. Cabi. 3rd ed.

Munoz, PR, et al., 2014 Unraveling additive from nonadditive effects using genomic relationship matrices. Genetics 198: 1759–1768. https://doi.org/10.1534/genetics.114.171322

R Core Team, 2016 R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria.

Resende, MF, et al., 2012 Accuracy of genomic selection methods in a standard data set of loblolly pine (Pinus taeda l.). Genetics 190: 1503–1510. https://doi.org/10.1534/genetics.111.137026

Slater, AT, et al., 2014 Improving the analysis of low heritability complex traits for enhanced genetic gain in potato. Theoretical and applied genetics 127: 809–820. https://doi.org/10.1007/s00122-013-2258-7

Slater AT, et al., 2016 Improving genetic gain with genomic selection in autotetraploid potato. The Plant Genome 9. https://doi.org/10.3835/plantgenome2016.02.0021

Su, G, et al., 2012 Estimating additive and non-additive genetic variances and predicting genetic merits using genome-wide dense single nucleotide polymorphism markers. PloS one 7:e45293. https://doi.org/10.1371/journal.pone.0045293

VanRaden, P, 2008 Efficient methods to compute genomic predictions. Journal of dairy science 91: 4414–4423. https://doi.org/10.3168/jds.2007-0980

Vitezica, ZG, et al., 2013 On the additive and dominant variance and covariance of individuals within the genomic selection scope. Genetics 195: 1223–1230. https://doi.org/10.1534/genetics.113.155176

Yang, J, et al., 2010 Common snps explain a large proportion of the heritability for human height. Nature genetics 42: 565–569. https://doi.org/10.1038/ng.608

#To knit an this vignette into an .R file
knitr::purl("vignettes/Tutorial_AGHmatrix.Rmd")

sessionInfo()

Try the AGHmatrix package in your browser

Any scripts or data that you put into this service are public.

AGHmatrix documentation built on July 31, 2019, 1:04 a.m.


text:
# Mariner 1

Mission type Launch of Mariner 1 Venus flyby NASA / JPL 4 minutes, 53 seconds Failed to orbit Mariner[citation needed] based on Ranger Block I Jet Propulsion Laboratory 202.8 kilograms (447 lb) 220 watts (at Venus encounter) July 22, 1962, 09:21:23 UTC Atlas LV-3 Agena-B Cape Canaveral LC-12

Mariner 1 was the first spacecraft of the American Mariner program, designed for a planetary flyby of Venus. It cost \$18.5 million in 1962. It was launched aboard an Atlas-Agena rocket on July 22, 1962. Shortly after takeoff the rocket responded improperly to commands from the guidance systems on the ground, setting the stage for an apparent software-related guidance system failure.[1] With the craft effectively uncontrolled, a range safety officer ordered its destructive abort 294.5 seconds after launch.[2]

According to NASA's current account for the public:

The booster had performed satisfactorily until an unscheduled yaw-lift (northeast) maneuver was detected by the range safety officer. Faulty application of the guidance commands made steering impossible and were directing the spacecraft towards a crash, possibly in the North Atlantic shipping lanes or in an inhabited area. The destruct command was sent 6 seconds before separation, after which the launch vehicle could not have been destroyed. The radio transponder continued to transmit signals for 64 seconds after the destruct command had been sent.[1]

The role of software error in the launch failure remains somewhat mysterious in nature, shrouded in the ambiguities and conflicts among (and in some accounts, even within) the various accounts, official and otherwise. The probe's mission was accomplished by Mariner 2 which launched 5 weeks later.

## Spacecraft and subsystems

The Mariner 1 spacecraft was identical to Mariner 2, launched 27 August 1962. Mariner 1 consisted of a hexagonal base, 1.04 meters [m] (3.41 ft) across and 0.36 m thick (1.2 ft), which contained six magnesium chassis housing the electronics for the science experiments, communications, data encoding, computing, timing, and attitude control and the power control, battery, and battery charger, as well as the attitude control gas bottles and the rocket engine. On top of the base, was a tall pyramid-shaped mast on which the science experiments were mounted which brought the total height of the spacecraft to 3.66 m (12.0 ft). Attached to either side of the base were rectangular solar panel wings with a total span of 5.05 meters and width of 0.76 meters (16.6 ft × 2.5 ft). Attached by an arm to one side of the base and extending below the spacecraft was a large directional dish antenna.

The Mariner 1 power system consisted of the two solar cell wings, one 183 × 76 cm (72 × 30 in) and the other, 152 × 76 cm (60 × 30 in), with a 31 cm (12 in) dacron extension (a solar sail) to balance the solar pressure on the panels. Those panels powered the craft directly or recharged a 1,000-watt-hour sealed silver-zinc cell battery, which was to be used before the panels were deployed, when the panels were not illuminated by the Sun, and when loads were heavy. A power-switching and booster regulator device controlled the power flow. Communications consisted of a 3-watt transmitter capable of continuous telemetry operation, the large high gain directional dish antenna, a cylindrical omnidirectional antenna at the top of the instrument mast, and two command antennas, one on the end of either solar panel, which received instructions for midcourse maneuvers and other functions.

Propulsion for midcourse maneuvers was supplied by a monopropellant (anhydrous hydrazine) 225 N retro-rocket. The hydrazine was ignited using nitrogen tetroxide and aluminium oxide pellets, and thrust direction was controlled by four jet vanes situated below the thrust chamber. Attitude control with a 1 degree pointing error was maintained by a system of nitrogen gas jets. The Sun and Earth were used as references for attitude stabilization. Overall timing and control was performed by a digital Central Computer and Sequencer. Thermal control was achieved through the use of passive reflecting and absorbing surfaces, thermal shields, and movable louvers.

The scientific experiments were mounted on the instrument mast and base. A magnetometer was attached to the top of the mast below the omnidirectional antenna. Particle detectors were mounted halfway up the mast, along with the cosmic ray detector. A cosmic-dust detector and solar plasma spectrometer/detector were attached to the top edges of the spacecraft base. A microwave radiometer and an infrared radiometer and the radiometer reference horns were rigidly mounted to a 48 cm (18.9 in) diameter parabolic radiometer antenna mounted near the bottom of the mast.

In addition, a small 91 × 150 cm (3-by-5-foot) United States flag was folded and stowed onboard Mariner 1 (and Mariner 2), before it was mated to the Agena.

## Launch failure

The launch was aborted due to a combination of two failures, an antenna hardware failure and an onboard guidance system software failure.

First, "the guidance antenna on the Atlas performed poorly, below specifications. When the signal received by the rocket became weak and noisy, the rocket lost its lock on the ground guidance signal that supplied steering commands."[3]

As a result, the rocket had to rely on its onboard guidance system, which had a bug in it. There are differing accounts of the details of this error.

### Over bar transcription error

The most detailed and consistent account was that the error was in hand-transcription of a mathematical symbol in the program specification for the guidance system, in particular a missing overbar.

The error had occurred when a symbol was being transcribed by hand in the specification for the guidance program. The writer missed the superscript bar (or overline) in

${\displaystyle {\bar {{\dot {R}}_{n}}}}$

by which was meant "the nth smoothed value of the time derivative of a radius R". Since the smoothing function indicated by the bar was left out of the specification for the program, the implementation treated normal minor variations of velocity as if they were serious, causing spurious corrections that sent the rocket off course.[4][5][6] It was then destroyed by the Range Safety Officer.[7]

### Alternate guidance system failure explanations

The cryptic nature of the problems that led to the decision to abort Mariner 1, as well as the confusion in various reports on the incident, led to other explanations in the popular press.

#### "The most expensive hyphen in history"

Many accounts note a missing "hyphen" ('-') rather than the over bar, in either the equations, the computer instructions or the data. For example, Arthur C. Clarke wrote several years later that Mariner 1 was "wrecked by the most expensive hyphen in history".[8]

Several factors contributed to the "missing hyphen" narrative and its longevity, even in official accounts from technical cognoscenti at JPL and NASA. Among the factors cited (or obvious enough):

• The overbar's resemblance to a hyphen ('‾' versus '-').
• The difficulty of explaining the real error to the American public and its elected representatives.
• External political pressures and internal schedule pressures, as the mission was
• an expensive failure of a three-way collaboration (JPL, NASA, USAF),
• legitimized within the narrative of the US-USSR space race,
• very high profile, as America's first planetary mission,
• on a very tight schedule, as it was planned with a narrow launch window (45 days), leaving little time for inquiries, investigations or recriminations before the launch of Mariner 2. The official accounts (which included mentions of a missing hyphen) were the results of an inquiry conducted in less than a week.

Regardless of whatever may have given rise to initial reports of a "missing hyphen", the simplest and most consistent-sounding explanation that the public and Congress would accept would probably have been preferable to those who simply wanted to get on with the job of a Venus fly-by mission. The stories had contradictions, perhaps, but they were so technical that nobody who could have interfered with Mariner-program progress was likely to care about them or even notice. (After all, even in one later NASA account, the supposed "hyphen" is reported as missing from instructions at one point in the text, and from equations at another[3]).

#### Ambiguity of error location

The New York Times, reporting on the results of a review board, said that the error stemmed from "the omission of a hyphen in some mathematical data" .[9] The same report also said the hyphen was

a symbol that should have been fed into a computer, along with a mass of other coded mathematical instructions.

This sort of inconsistency or ambiguity was seen in many subsequent variations on the story, official and otherwise. "Missing hyphen" versions of the story gained from official support before the month was out. NASA official Richard B. Morrison testified before Congress that the supposed hyphen

... gives a cue for the spacecraft to ignore the data the computer feeds it until radar contact is once again restored. When that hyphen is left out, false information is fed into the spacecraft control systems. In this case, the computer fed the rocket in hard left, nose down and the vehicle obeyed and crashed.[10]

(Note that Morrison says the spacecraft "crashed", not that it was intentionally destroyed). In a NASA account submitted to Congress in 1963, the hyphen is described as missing in two different ways:

NASA-JPL-USAF Mariner R-1 Post-Flight Review Board determined that the omission of a hyphen in coded computer instructions transmitted incorrect guidance signals to Mariner spacecraft boosted by two-stage Atlas-Agena from Cape Canaveral on July 21. Omission of hyphen in data editing caused computer to swing automatically into a series of unnecessary course correction signals which threw spacecraft off course so that it had to be destroyed.[11]

In the same 1963 report to Congress, Morrison's testimony from the previous year is recounted differently:

In testimony before House Science and Astronautics Committee, Richard B. Morrison, NASA's Launch Vehicles Director, testified that an error in computer equations for Venus probe launch of Mariner R-1 space-craft on July 21 led to its destruction when it veered off course.[12]

JPL's Mariner Venus Final Project Report in 1965 noted that, at 4 minutes and 25 seconds into the flight, there was an "[U]nscheduled yaw-lift maneuver":

...steering commands were being supplied, but faulty application of the guidance equations was taking the vehicle far off course.[13]

In a NASA report published in 1985, Oran Nicks offered another slightly differing account, but with the software-related error still identified as a missing "hyphen":

The guidance antenna on the Atlas performed poorly, below specifications. When the signal received by the rocket became weak and noisy, the rocket lost its lock on the ground guidance signal that supplied steering commands. The possibility had been foreseen; in the event that radio guidance was lost the internal guidance computer was supposed to reject the spurious signals from the faulty antenna and proceed on its stored program, which would probably have resulted in a successful launch. At this point a second fault took effect. Somehow a hyphen had been dropped from the guidance program loaded aboard the computer, allowing the flawed signals to command the rocket to veer left and nose down. The hyphen had been missing on previous successful flights of the Atlas, but that portion of the equation had not been needed since there was no radio guidance failure.[3]

NASA's website now says the problem was:

... apparently caused by a combination of two factors. Improper operation of the Atlas airborne beacon equipment resulted in a loss of the rate signal from the vehicle for a prolonged period. The airborne beacon used for obtaining rate data was inoperative for four periods ranging from 1.5 to 61 seconds in duration. Additionally, the Mariner 1 Post Flight Review Board determined that the omission of a hyphen in coded computer instructions in the data-editing program allowed transmission of incorrect guidance signals to the spacecraft. During the periods the airborne beacon was inoperative the omission of the hyphen in the data-editing program caused the computer to incorrectly accept the sweep frequency of the ground receiver as it sought the vehicle beacon signal and combined this data with the tracking data sent to the remaining guidance computation. This caused the computer to swing automatically into a series of unnecessary course corrections with erroneous steering commands which finally threw the spacecraft off course.[14]

#### Other punctuation

In other accounts, the bug consisted of:

• a period typed in place of a comma, causing a FORTRAN DO loop statement to be misinterpreted (although there is no evidence that FORTRAN was used in the mission), of the form "DO 5  K=1. 3" interpreted as assignment "DO5K = 1.3"[15] There are anecdotal reports that there was in fact such a bug in a NASA orbit computation program at about this time, but it was a program for Project Mercury, not Mariner, and the claim was that the bug was noticed and fixed before there could be any serious consequences.[16]
• a missing comma [17]
• an extraneous semicolon [18]

## References

1. ^ a b "Mariner 1". 4.0.8. NASA. 2008-08-05. Retrieved 2009-02-14.
2. ^ "Venus Shot Fails as Rocket Strays" (fee required). New York Times. 1962-07-23. Retrieved 2009-02-14.
3. ^ a b c NASA publication SP-480, Far Travelers -- The Exploring Machines, Oran W. Nicks, 1985
4. ^ Peter Neumann (1989-05-27). "Mariner I -- no holds BARred". The Risks Digest Volume 8: Issue 75. Retrieved 2014-10-31.
5. ^ Ceruzzi, Paul E. Ceruzzi (1989). Beyond the Limits: Flight Enters the Computer Age. ISBN 978-0262530828.
6. ^ http://www.faqs.org/faqs/space/probe/
7. ^ Beyond the Limits: Flight Enters the Computer Age, Paul E. Ceruzzi, p.203. In one of the notes for this book (p. 250), the author writes "The same flawed program had been used in earlier Ranger launches with no ill effects."
8. ^ The Promise of Space, Arthur C. Clarke, 1968, p. 225.
9. ^ "For Want of Hyphen Venus Rocket Is Lost", New York Times, July 27, 1962, as quoted in RISKS Digest, Vol 5, Issue #66.
10. ^ House Science and Astronautics Committee, July 31, 1962, also quoted here
11. ^ "Astronautical and Aeronautical Events of 1962," report to the House Committee on Science and Astronautics, June 12, 1963 p.131.
12. ^ "Astronautical and Aeronautical Events of 1962," report to the House Committee on Science and Astronautics, June 12, 1963 p.333
13. ^
14. ^ "Mariner 1", Version 4.0.7, 2 April 2008.
15. ^ Beyond the Limits: Flight Enters the Computer Age, Paul E. Ceruzzi, In p.250, footnote 13 for Chapter 9, where Ceruzzi writes that, "[S]ince the Atlas Guidance Computer did not have a Fortran compiler ....", and in footnote 14, "The Atlas Launch computer did not even use Fortran, the Fortran programming language. How the story has become embellished in this way is a mystery."
16. ^ RISKS Digest, v. 9, issue 54, "Mariner I [once more]", Mark Brader, 12 December 1989.
17. ^ Famous bugs
18. ^ JPL 101 page 22

format: plain


text:
It is currently 21 Feb 2019, 19:44

### GMAT Club Daily Prep

#### Thank you for using the timer - this advanced tool can estimate your performance and suggest more practice questions. We have subscribed you to Daily Prep Questions via email.

Customized
for You

we will pick new questions that match your level based on your Timer History

Track

every week, we’ll send you an estimated GMAT score based on your performance

Practice
Pays

we will pick new questions that match your level based on your Timer History

# QOTD # 15 The greatest of the 21 positive integers in a cert

Author Message
TAGS:
Moderator
Joined: 18 Apr 2015
Posts: 5586
Followers: 89

Kudos [?]: 1118 [1] , given: 5174

QOTD # 15 The greatest of the 21 positive integers in a cert [#permalink]  10 Sep 2016, 02:04
1
KUDOS
Expert's post
00:00

Question Stats:

83% (01:52) correct 16% (02:02) wrong based on 18 sessions
The greatest of the 21 positive integers in a certain list is 16. The median of the 21 integers is 10. What is the least possible average (arithmetic mean) of the 21 integers?

A) 4
B) 5
C) 6
D) 7
E) 8

Practice Questions
Question: 15
Page: 180
[Reveal] Spoiler: OA

_________________
Moderator
Joined: 18 Apr 2015
Posts: 5586
Followers: 89

Kudos [?]: 1118 [2] , given: 5174

Re: QOTD # 15 The greatest of the 21 positive integers in a cert [#permalink]  10 Sep 2016, 02:06
2
KUDOS
Expert's post
Explanation

You are given that the median of the 21 positive integers is 10 and the greatest of the 21 integers is 16. This means that when the 21 integers are listed in order from least to greatest,

• the 1st through 10th integers are between 1 and 10, inclusive;
• the 11th integer is 10;
• the 12th through 20th integers are between 10 and 16, inclusive; and
• the 21st integer is 16.

The least possible average of the 21 integers would be achieved by using the least possible value of each integer as described above in the reordered list:

• the 1st through 10th integers would each be 1;
• the 11th integer would be 10;
• the 12th through 20th integers would each be 10; and
• the 21st integer would be 16.

For the least possible integers, the sum is (10)(1) + 10 + (9)(10) + 16, or 126. Therefore the least possible average is $$\frac{126}{21}$$ or 6.

The correct answer is Choice C.
_________________
GRE Instructor
Joined: 10 Apr 2015
Posts: 1439
Followers: 54

Kudos [?]: 1368 [1] , given: 8

Re: QOTD # 15 The greatest of the 21 positive integers in a cert [#permalink]  19 Sep 2016, 17:00
1
KUDOS
Expert's post
Carcass wrote:
The greatest of the 21 positive integers in a certain list is 16. The median of the 21 integers is 10. What is the least possible average (arithmetic mean) of the 21 integers?

A) 4
B) 5
C) 6
D) 7
E) 8

Let the following spaces represent the 21 integers listed in ASCENDING ORDER, with a red space indicating the median:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

The greatest of the 21 positive integers in a certain list is 16
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 16

The median of the 21 integers is 10
_ _ _ _ _ _ _ _ _ _ 10 _ _ _ _ _ _ _ _ _ 16

What is the least possible average (arithmetic mean) of the 21 integers?
We must MINIMIZE the 19 remaining integers.
So, the first 10 integers must be 1, since 1 is the smallest positive integer.
1 1 1 1 1 1 1 1 1 1 10 _ _ _ _ _ _ _ _ _ 16

The remaining integers must be greater than or equal to 10 and less than or equal to 16
Since, we're trying to MINIMIZE the remaining integers, we'll let each number be 10 to get:
1 1 1 1 1 1 1 1 1 1 10 10 10 10 10 10 10 10 10 10 16

Average = (1+1+1+1+1+1+1+1+1+1+10+10+10+10+10+10+10+10+10+10+16)/21
= 126/21
= 6

[Reveal] Spoiler:
C

RELATED VIDEO

_________________

Brent Hanneson – Creator of greenlighttestprep.com

Target Test Prep Representative
Affiliations: Target Test Prep
Joined: 09 May 2016
Posts: 161
Location: United States
Followers: 4

Kudos [?]: 120 [1] , given: 0

Re: QOTD # 15 The greatest of the 21 positive integers in a cert [#permalink]  04 May 2018, 09:21
1
KUDOS
Expert's post
Carcass wrote:
The greatest of the 21 positive integers in a certain list is 16. The median of the 21 integers is 10. What is the least possible average (arithmetic mean) of the 21 integers?

A) 4
B) 5
C) 6
D) 7
E) 8

There are 21 numbers in the list, and, if we list the numbers in ascending order, the median is the 11th number.

Thus, we can let each of the first 10 numbers = 1, each of the next 10 numbers = 10, and the last number = 16.

Thus, the average is (10 x 1 + 10 x 10 + 16)/21 = 126/21 = 6.

_________________

Jeffery Miller

GRE Quant Self-Study Course
500+ lessons 3000+ practice problems 800+ HD solutions

Re: QOTD # 15 The greatest of the 21 positive integers in a cert   [#permalink] 04 May 2018, 09:21
Display posts from previous: Sort by


text:
zbMATH — the first resource for mathematics

On a class of third-order nonlinear difference equations. (English) Zbl 1178.39011
The topic of the paper is the third order rational difference (or iteration) equation $x_{n+1} = A + \frac{x_n^p}{x_{n-1}^q x_{n-2}^r}, \quad n \in \mathbb{N}_0.$ The authors present five theorems containing some conditions on the positive parameters $$p,q,r$$ and $$A$$ that assure either unboundedness of at least one solution or boundedness of all solutions.

MSC:
 39A20 Multiplicative and other generalized difference equations, e.g., of Lyness type 39A22 Growth, boundedness, comparison of solutions to difference equations
Full Text:
References:
 [1] Berenhaut, K.; Foley, J.; Stević, S., The global attractivity of the rational difference equation $$y_n = 1 +(y_{n - k} / y_{n - m})$$, Proc. am. math. soc., 135, 1133-1140, (2007) · Zbl 1109.39004 [2] Berenhaut, K.; Foley, J.; Stević, S., The global attractivity of the rational difference equation $$y_n = A +(y_{n - k} / y_{n - m})^p$$, Proc. am. math. soc., 136, 103-110, (2008) · Zbl 1134.39002 [3] Berenhaut, K.S.; Stević, S., A note on positive nonoscillatory solutions of the difference equation $$x_{n + 1} = \alpha +(x_{n - k}^p / x_n^p)$$, J. differ. eqs. appl., 12, 5, 495-499, (2006) · Zbl 1095.39004 [4] Berenhaut, K.; Stević, S., The behaviour of the positive solutions of the difference equation $$x_n = A +(x_{n - 2} / x_{n - 1})^p$$, J. differ. eqs. appl., 12, 9, 909-918, (2006) · Zbl 1111.39003 [5] Berenhaut, K.; Stević, S., The difference equation $$x_{n + 1} = \alpha + \left(x_{n - k} / \sum_{i = 0}^{k - 1} c_i x_{n - i}\right)$$ has solutions converging to zero, J. math. anal. appl., 326, 1466-1471, (2007) · Zbl 1113.39003 [6] Berezansky, L.; Braverman, E., On impulsive beverton – holt difference equations and their applications, J. differ. eqs. appl., 10, 9, 851-868, (2004) · Zbl 1068.39005 [7] Berezansky, L.; Braverman, E., Sufficient conditions for the global stability of nonautonomous higher order difference equations, J. differ. eqs. appl., 11, 9, 785-798, (2005) · Zbl 1078.39005 [8] Berg, L., On the asymptotics of nonlinear difference equations, Z. anal. anwendungen, 21, 4, 1061-1074, (2002) · Zbl 1030.39006 [9] Berg, L., Inclusion theorems for non-linear difference equations with applications, J. differ. eqs. appl., 10, 4, 399-408, (2004) · Zbl 1056.39003 [10] Berg, L., Oscillating solutions of rational difference equations, Rostock. math. kolloq., 58, 31-35, (2004) · Zbl 1096.39002 [11] Berg, L., Nonlinear difference equations with periodic solutions, Rostock. math. kolloq., 61, 12-19, (2005) [12] Berg, L., On the asymptotics of difference equation $$x_{n - 3} = x_n(1 + x_{n - 1} x_{n - 2})$$, J. differ. eqs. appl., 14, 1, 105-108, (2008) · Zbl 1138.39003 [13] Berg, L.; Stević, S., Periodicity of some classes of holomorphic difference equations, J. differ. eqs. appl., 12, 8, 827-835, (2006) · Zbl 1103.39004 [14] Berg, L.; Stević, S., Linear difference equations mod 2 with applications to nonlinear difference equations, J. differ. eqs. appl., 14, 7, 693-704, (2008) · Zbl 1156.39003 [15] De la Sen, M., About the properties of a modified generalized beverton – holt equation in ecology models, Discrete dyn. nat. soc., 2008, 23, (2008), Article ID 592950 · Zbl 1148.92031 [16] De la Sen, M.; Alonso-Quesada, S., A control theory point of view on beverton – holt equation in population dynamics and some of its generalizations, Appl. math. comput., 199, 2, 464-481, (2008) · Zbl 1137.92034 [17] DeVault, R.; Kent, C.; Kosmala, W., On the recursive sequence $$x_{n + 1} = p +(x_{n - k} / x_n)$$, J. differ. eqs. appl., 9, 8, 721-730, (2003) · Zbl 1049.39026 [18] Feuer, J., On the behaviour of solutions of $$x_{n + 1} = p +(x_{n - 1} / x_n)$$, Appl. anal., 83, 6, 599-606, (2004) · Zbl 1053.39009 [19] Gutnik, L.; Stević, S., On the behaviour of the solutions of a second-order difference equation, 2007, 14, (2007), Article ID 27562 · Zbl 1180.39002 [20] Hu, L.H.; Li, W.T.; Stević, S., Global asymptotic stability of a second order rational difference equation, J. differ. eqs. appl., 14, 8, 779-797, (2008) · Zbl 1153.39015 [21] Iričanin, B., A global convergence result for a higher-order difference equation, Discrete dyn. nat. soc., 2007, 7, (2007), Article ID 91292 · Zbl 1180.39003 [22] Karakostas, G.L., Convergence of a difference equation via the full limiting sequences method, Differ. eqs. dyn. syst., 1, 4, 289-294, (1993) · Zbl 0868.39002 [23] Karakostas, G.L., Asymptotic 2-periodic difference equations with diagonally self-invertible responses, J. differ. eqs. appl., 6, 329-335, (2000) · Zbl 0963.39020 [24] Karakostas, G.L., Asymptotic behavior of the solutions of the difference equation $$x_{n + 1} = x_n^2 f(x_{n - 1})$$, J. differ. eqs. appl., 9, 6, 599-602, (2003) · Zbl 1045.39006 [25] Mishkis, A.D., On some problems of the theory of differential equations with deviating argument, Uspekhi mat. nauk, 32:2, 194, 173-202, (1977) [26] Ozban, A.Y., On the system of rational difference equations $$x_n = a / y_{n - 3}, y_n = \mathit{by}_{n - 3} / x_{n - q} y_{n - q}$$, Appl. math. comput., 188, 1, 833-837, (2007) · Zbl 1123.39006 [27] Ozen, S.; Ozturk, I.; Bozkurt, F., On the recursive sequence $$y_{n + 1} = (\alpha + y_{n - 1}) /(\beta + y_n) + y_{n - 1} / y_n$$, Appl. math. comput., 188, 1, 180-188, (2007) · Zbl 1123.39007 [28] Pielou, E.C., An introduction to mathematical ecology, (1969), Wiley Interscience · Zbl 0259.92001 [29] Pielou, E.C., Population and community ecology, (1974), Gordon and Breach · Zbl 0349.92024 [30] E.P. Popov, Automatic Regulation and Control, Nauka, Moscow, Russia, 1966, Russian. [31] Stević, S., Behaviour of the positive solutions of the generalized beddington – holt equation, Panamer. math. J., 10, 4, 77-85, (2000) · Zbl 1039.39005 [32] Stević, S., Asymptotic behaviour of a sequence defined by iteration with applications, Colloq. math., 93, 2, 267-276, (2002) · Zbl 1029.39006 [33] Stević, S., A global convergence results with applications to periodic solutions, Indian J. pure appl. math., 33, 1, 45-53, (2002) · Zbl 1002.39004 [34] Stević, S., Asymptotic behaviour of a nonlinear difference equation, Indian J. pure appl. math., 34, 12, 1681-1687, (2003) · Zbl 1049.39012 [35] Stević, S., On the recursive sequence $$x_{n + 1} = \left(A / \prod_{i = 0}^k x_{n - i}\right) + \left(1 / \prod_{j = k + 2}^{2(k + 1)} x_{n - j}\right)$$, Taiwanese J. math., 7, 2, 249-259, (2003) [36] Stević, S., A note on periodic character of a difference equation, J. differ. eqs. appl., 10, 10, 929-932, (2004) · Zbl 1057.39005 [37] Stević, S., On the recursive sequence $$x_{n + 1} = \alpha +(x_{n - 1}^p / x_n^p)$$, J. appl. math. comput., 18, 1-2, 229-234, (2005) · Zbl 1078.39013 [38] Stević, S., On the recursive sequence $$x_{n + 1} = (\alpha + \beta x_{n - k}) / f(x_n, \ldots, x_{n - k + 1})$$, Taiwanese J. math., 9, 4, 583-593, (2005) · Zbl 1100.39014 [39] Stević, S., A short proof of the cushing – henson conjecture, Discrete dyn. nat. soc., 2006, 5, (2006), Article ID 37264 · Zbl 1149.39300 [40] Stević, S., Asymptotic behaviour of a class of nonlinear difference equations, Discrete dyn. nat. soc., 2006, 10, (2006), Article ID 47156 [41] Stević, S., Global stability and asymptotics of some classes of rational difference equations, J. math. anal. appl., 316, 60-68, (2006) · Zbl 1090.39009 [42] Stević, S., On positive solutions of a $$(k + 1)$$th order difference equation, Appl. math. lett., 19, 5, 427-431, (2006) · Zbl 1095.39010 [43] Stević, S., Asymptotics of some classes of higher order difference equations, Discrete dyn. nat. soc., 2007, 20, (2007), Article ID 56813 · Zbl 1180.39009 [44] Stević, S., Existence of nontrivial solutions of a rational difference equation, Appl. math. lett., 20, 28-31, (2007) · Zbl 1131.39009 [45] Stević, S., On the recursive sequence $$x_{n + 1} = A +(x_n^p / x_{n - 1}^r)$$, Discrete dyn. nat. soc., 2007, 9, (2007), Article ID 40963 · Zbl 1151.39011 [46] Stević, S., On the recursive sequence $$x_n = 1 + \left(\sum_{i = 1}^k \alpha_i x_{n - p_i} / \sum_{j = 1}^m \beta_j x_{n - q_j}\right)$$, Discrete dyn. nat. soc., 2007, 7, (2007), Article ID 39404 [47] Stević, S., Boundedness and global stability of a higher-order difference equation, J. differ. eqs. appl., 14, 10-11, 1035-1044, (2008) · Zbl 1161.39011 [48] Stević, S., On the difference equation $$x_{n + 1} = \alpha +(x_{n - 1} / x_n)$$, Comput. math. appl., 56, 5, 1159-1171, (2008) · Zbl 1155.39305 [49] Stević, S., Boundedness character of a class of difference equations, Nonlin. anal. TMA, 70, 839-848, (2009) · Zbl 1162.39011 [50] Yang, Y.; Yang, X., On the difference equation $$x_{n + 1} = (\mathit{px}_{n - s} + x_{n - t}) /(\mathit{qx}_{n - s} + x_{n - t})$$, Appl. math. comput., 203, 2, 903-907, (2008) · Zbl 1162.39015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Find Function Always at Distance from Another Function

I changed the title to hopefully clarify a bit: What i am trying to do is find a function that is always at a specific distance from another function i.e. a function where a drawn circle with radius $r=1$ with center on the function will always be tangented by another function. Read below for background info and what i started off writing (not necessary to know).

I want to make a circle run on a given function. What i have in mind is having a circle from the implicit function $(a-x)^2+(b-y)^2=r^2$ where i use $r=1$ and $a$ and $b$ are the $x$ and $y$ coordinates of the center of the circle, respectively. I would like to try with the parabola $f(x)=-x^2+2$ and i am mainly focusing on the interval $-5\leq x\leq 5$. I found it working to use the distance formula, $\sqrt{(a-x)^2+(b-f(x))^2}$ to plot how far away the circle center is from the function $f(x)$ at a given $x$. This may seem chaotic, so here is a picture of what i mean

Purple is the distance formula function while grey is the derivative of that

Now i am currently having a hard time wrapping my head around this, but i think i want to find a b-value (height of the circle center) where the distance at minimum is 1 (i.e. the purple function has a minimum of $y=1$ exactly.) So i want to find a b-value where the purple function is 1 while the grey function is 0. How do i do this? Is there a smarter way?

• Your question isn't 100% clear, but are you asking how to construct a parallel curve? – Michael Seifert Nov 7 '17 at 21:18
• No, i would like a function g(x) where the closest point to another function f(x) is always the same distance. Imagine a function on which you draw infinitely many circles. Now create a function that is tangent to all of those circles. I want to create that function based on f(x) being a parabola, – iBoughtWinrar Nov 7 '17 at 21:28
• You just gave an exact description of a parallel curve; take a look at the link in my previous comment. I'll write up a brief answer to show how it's done in your case, but note that in general there isn't a nice answer of the form $y = g(x)$. – Michael Seifert Nov 7 '17 at 21:32
• Ah, my bad, i assumed too much from the word parallel – iBoughtWinrar Nov 7 '17 at 21:36

What you're looking for is a parallel curve. In your case, you would parametrize the parabola as \begin{align} x(t) &= t & y(t) &= -t^2 + 2 \end{align} The parallel curves would then be \begin{align} X(t) &= t - \frac{2rt}{\sqrt{4t^2 + 1}} & Y(t) &= -t^2+2 - \frac{r}{\sqrt{4t^2 + 1}}, \end{align} where $r$ is the desired radius of the circles along the curve. This gives you the parallel curve along one "side" of the original curve; for the other one, flip the sign of $r$ in each of the above equations.
Note that the curve "inside" the parabola can't be possibly be expressed in the form $Y = g(X)$--there are multiple values of the $Y$ coordinate for some values of $X$. The "outside" parallel curve is better-behaved, but I still suspect that it can't be expressed in a nice form $Y(X)$; at best, you might be able to end up with a relation between $X$ and $Y$ where you can show that some polynomial in $X$ and $Y$ must vanish, but you can't solve it for $X$ or $Y$ explicitly.
• If anyone can figure out what the above-mentioned relation between $X$ and $Y$ should be, feel free to edit this answer to include it or post it as a comment below. – Michael Seifert Nov 7 '17 at 21:58


text:
Want to ask us a question? Click here
Browse Questions
 Ad
Home  >>  AIMS
0 votes

# Evaluate $7p^2x-(-4qy^2)$,given that $p=-2,q=1,x=3$ and $y=-4$

$\begin{array}{1 1}(A)\;-4&(B)\;84\\(C)\;20&(D)\;148\end{array}$

Can you answer this question?

## 1 Answer

0 votes
148
Hence (D) is the correct answer.
answered Apr 11, 2014


text:
main-content

## Über dieses Buch

This book collects the notes of the lectures given at an Advanced Course on Dynamical Systems at the Centre de Recerca Matemàtica (CRM) in Barcelona. The notes consist of four series of lectures.

The first one, given by Andrew Toms, presents the basic properties of the Cuntz semigroup and its role in the classification program of simple, nuclear, separable C*-algebras. The second series of lectures, delivered by N. Christopher Phillips, serves as an introduction to group actions on C*-algebras and their crossed products, with emphasis on the simple case and when the crossed products are classifiable. The third one, given by David Kerr, treats various developments related to measure-theoretic and topological aspects of crossed products, focusing on internal and external approximation concepts, both for groups and C*-algebras. Finally, the last series of lectures, delivered by Thierry Giordano, is devoted to the theory of topological orbit equivalence, with particular attention to the classification of minimal actions by finitely generated abelian groups on the Cantor set.

## Inhaltsverzeichnis

### Chapter 1. Introduction

Abstract
This part of the Advanced Course is meant to introduce the reader to an invariant for C*-algebras —the Cuntz semigroup— which has recently come to the forefront of research on C*-algebra classification. In order to motivate its introduction we return to the roots of the theory of operator algebras, and to the type classification of factors in particular.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 2. The Cuntz Semigroup

Abstract
Here, we introduce the basic theory of the Cuntz semigroup. Any proofs not contained in these notes can be found in Ara–Brown–Guido–Lledo–Perera–Toms [1], but no originality is claimed there. Most of the results here are due to Cuntz [9], Kirchberg–Rørdam [17], and Rørdam [26]. We assume that all C*-algebras are separable unless otherwise noted.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 3. Structure of the Cuntz Semigroup

Abstract
What does the Cuntz semigroup really look like? We will see later that the question is out of reach in any reasonable sense without imposing some conditions on your C*-algebra. For this section, we restrict our attention to unital simple separable C*-algebras which have strict comparison of positive elements. In light of Example 2.0.5, we will also assume that our algebra is stably finite, since the Cuntz semigroup is otherwise degenerate. This means that our algebra admits at least one normalized 2-quasitrace (which will be a trace if the algebra is exact). The material covered in this section can be found in Brown–Perera–Toms [4] and Brown–Toms [5].
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 4. Elliott’s Program

Abstract
The Elliott invariant of a C*-algebra A is the 4-tuple
$$\mathrm{Ell}(\mathit{A})\,\, : = \,\, \left(\left(\mathrm{K}_0\mathit{A}, \mathrm{K}_0\mathit{A}^{+}, \sum{}_{\mathit{A}}\right), \mathrm{K}_1\mathit{A}, \,\mathrm{T}^{+}\,(\mathit{A}), \rho\mathit{A} \right),$$
(4.1)
where the K-groups are the Banach algebra ones, K0A+ is the image of the Murray–von-Neumann semigroup V(A) under the Grothendieck map, $$\sum{}_\mathit{A}$$ is the subset of K0A corresponding to projections in A, T+(A) is the space of positive tracial linear functionals on A, and ρA is the natural pairing of T+(A) and K0A given by evaluating a trace at a K0-class. The reader is referred to Rørdam’s monograph [27] for a detailed treatment of this invariant. In the case of a unital C*-algebra, the invariant becomes $$\left(\left(\mathrm{K}_0{\mathit{A}}, \mathrm{K}_0{\mathit{A}^{+}}, [{1}_{\mathit{A}}]\right), {\mathrm{K}_1}\mathit{A}, \, \mathrm{T}\,(\mathit{A}), \rho\mathit{A}\right),$$, where [1A] is the K0-class of the unit, and T(A) is the (compact convex) space of tracial states. We will concentrate on unital C*-algebras in the sequel in order to limit technicalities.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 5. A New Conjecture

Abstract
The appearance of counterexamples to (EC) in the first half of the 2000s forced a re-evaluation of the classification program Elliott–Toms [14]. The fact that so many natural classes of C*-algebras do satisfy (EC) made it impossible to believe that instances of its confirmation were somehow random. There had to be an underlying principle governing the existing theory and clarifying the line between those algebras which do and do not satisfy (EC). In this section we will introduce and discuss a conjectural version of such a principle, one that has significant evidence to support it. The conjecture relates three regularity properties for C*-algebras which we introduce presently.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 6. Nuts and Bolts: Proof Sketches

Abstract
In this section we take some of the salient results of the preceding section and show more or less how they are proved. We shall take for granted, however, Winter’s locally finite nuclear dimension theorem; a full proof is well beyond the scope of these notes.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 7. Introduction and Motivation

Abstract
These notes are an introduction to group actions on C*-algebras and their crossed products, primarily by discrete groups and with emphasis on situations in which the crossed products are simple and at least close to the class of C*-algebras expected to be classifiable in the sense of the Elliott program. They are aimed at graduate students who have had a one semester or one year course on the general theory of C*-algebras. (We give more details on the prerequisites later in this section.) These notes are not intended as a reference work. Our emphasis is on explaining ideas and methods, rather than on giving complete proofs. For some results, different proofs are given at different locations in these notes, or special cases are proved of results which are proved later in greater generality by quite different methods. For others, some of the main ideas are explained and simpler versions of some of the relevant lemmas are proved, but we refer to the research papers for the full proofs. Other results and calculations are left as exercises; the reader is strongly encouraged to do many of these, to develop facility with the material. Yet other results, needed for the proofs of the theorems described here but not directly related to dynamics, are quoted with only some general description, or with no background at all.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 8. Group Actions

Abstract
This is the first of three sections devoted to examples of group actions.
In this section, we give examples of actions on commutative C*-algebras. In Section 8.2 we give a variety of examples of actions on noncommutative C*- algebras, and in Section 8.3 we give an additional collection of examples of actions that are similar to gauge actions.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 9. Group C*-algebras and Crossed Products

Abstract
The main focus of these notes is the structure of certain kinds of crossed products. The C*-algebra of a group is a special case of a crossed product—it comes from the trivial action of the group on ℂ—but not one of the ones we are mainly concerned with. We devote this section and Section 9.3 to group C*-algebras anyway, in order to provide an introduction to crossed products in a simpler case, and because understanding the group C*-algebra is helpful, at least at a heuristic level, for understanding more general crossed products. Section 9.4 treats crossed product C*-algebras and Section 9.5 treats reduced crossed product C*-algebras. In Section 9.6 we give a number of explicit computations of crossed product C*- algebras. The brief Section 9.2 contains a proof that the reduced C*-algebra of a finitely generated nonabelian free group is simple.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 10. Some Structure Theory for Crossed Products by Finite Groups

Abstract
Our main interest is in structural results for crossed products. We want simplicity, but we really want much more than that. We particularly want theorems showing that certain crossed products are in classes of C*-algebras known to be covered by the Elliott classification program, so that the crossed product can be identified up to isomorphism by computing its K-theory and other invariants. In many cases, one settles for related weaker structural results, such as stable rank one, real rank zero, order on traces determined by projections, strict comparison of positive elements, or Z-stability. Some results with conclusions of this sort are stated in these notes, but mostly without proof.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 11. An Introduction to Crossed Products by Minimal Homeomorphisms

Abstract
In this section, we discuss free and essentially free minimal actions of countable discrete groups on compact metric spaces, with emphasis on minimal homeomorphisms (actions of ℤ). We give two simplicity proofs, using very different methods. One works for free minimal actions, and the method gives further information, as well as some information when the action is not minimal; see Theorems 11.1.20 and 11.1.22. The second proof is a special case of a more general simplicity theorem; the case we prove allows some simplification of the argument. Our theorem is Theorem 11.1.10, and its proof is given before Theorem 11.1.25. The full theorem is stated as Theorem 11.1.25. Both proofs end with an argument related to the proof that Kishimoto’s condition (see Definition 10.4.20) implies simplicity of the crossed product (see Theorem 10.4.22), but the two proofs use quite different routes to get there.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 12. An Introduction to Large Subalgebras and Applications to Crossed Products

Abstract
In this part, we give an introduction to large subalgebras of C*-algebras and some applications. Much of the text of this part is taken directly from [215], which is a survey of applications of large subalgebras based on lectures given at the University of Wyoming in the summer of 2015. That survey assumes much more background than these notes (it starts with the material here), there are some differences in the organization, and it contains some open problems and other discussion omitted here because they are too far off the topic of these notes.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 13. Introduction

Abstract
The aim of these notes is to survey several recent developments at the crossed product interface of the subjects of C*-algebras and group actions on compact spaces, especially in connection with the classification program for separable nuclear C*-algebras. Groups and group actions have from the beginning provided a rich source of examples in the theory of operator algebras, and the struggle to obtain an algebraic understanding of dynamical phenomena has to a great extent driven, and continues to drive, the development of structure and classification theory for both von Neumann algebras and C*-algebras. While our focus is on the topological realm of C*-algebras, we have nevertheless endeavored to take a broad perspective that incorporates both the measurable and the topological in a unifying framework. This enables us not only to illuminate the conceptual similarities and technical differences between the two sides, but also to emphasize that topological-dynamical and C*-algebraic concepts themselves can range from the more measure-theoretic (like entropy and nuclearity, which involve weak-type approximation of multiplicative structure or norm approximation of linear structure) to the more topological (like periodicity and approximate finite-dimensionality, which involve norm approximation of multiplicative structure). Thinking in such terms can be helpful for predicting and understanding the role of various phenomena in C*-classification theory.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 14. Internal Measure-Theoretic Phenomena

Abstract
The notion of amenability in its most basic combinatorial sense captures the idea of internal finite approximation from a measure-theoretic perspective. It plays a pivotal role not only in combinatorial and geometric group theory but also in the theory of operator algebras through its various linear manifestations like hyperfiniteness, semidiscreteness, injectivity, and nuclearity. In this section we will review the theory of amenability for discrete groups (see [34, 76] for general references), and then move in Section 14.2 to amenable actions and their reduced crossed products.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 15. External Measure-Theoretic Phenomena

Abstract
As discussed in Section 14.1, for discrete groups the basic idea of internal measuretheoretic finite approximation is captured by the Følner set characterization of amenability. At the same time we can view Følner sets as furnishing external finite approximations in the following way. Let F be a nonempty finite subset of a discrete group G.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 16. Internal Topological Phenomena

Abstract
The topological analogue of amenability for discrete groups is local finiteness. In contrast to the setting of C*-algebras, which we will turn to below, for discrete groups the topological notion of perturbation is trivial and thus, unlike the combinatorial measure-theoretic viewpoint, does not give us anything new beyond the merely group-theoretic. The group G is said to be locally finite if every finite subset of G generates a finite subgroup. Equivalently, G is the increasing union of finite subgroups. Obviously every finite group is locally finite. An example of a countably infinite locally finite group is the group of all permutations of N which fix all but finitely many elements. There are uncountably many pairwise nonisomorphic countable locally finite groups, and there is a countable locally finite group U which has the universal property that it contains a copy of every finite group and any two monomorphisms of a finite group into U are conjugate by an inner automorphism [47]. Note that every locally finite group is torsion. The converse is the general Burnside problem and is false, as was shown by Golod. In fact a torsion group need not even be amenable, which is the measure-theoretic analogue of local finiteness to be discussed below.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 17. External Topological Phenomena

Abstract
Complementing the internal finite modelling property of local finiteness is the external property of local embeddability into finite groups, which is the topological (i.e., purely group-theoretic, since our groups are discrete) analogue of soficity. The group G is said to be LEF (locally embeddable into finite groups) if for every finite set FG there is a finite group H and a map σ : GH such that σ(st) = σ(s)σ(t) for all s, tF and σ|F is injective. This notion was introduced by Gordon and Vershik in [33].
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 18. Introduction

Abstract
In 1959, Dye [19] introduced the notion of orbit equivalence and proved that any two ergodic finite measure preserving transformations on a Lebesgue space are orbit equivalent. In [20], he had also conjectured that an arbitrary ergodic action of a discrete amenable group is orbit equivalent to a ℤ–action. This conjecture was proved in Ornstein–Weiss [73]. The most general case was proved in Connes– Feldman–Weiss [13] by establishing that an amenable nonsingular countable equivalence relation $$\mathcal{R}$$ can be generated by a single transformation, or equivalently, is hyperfinite, i.e., $$\mathcal{R}$$ is up to a null set, a countable increasing union of finite equivalence relations.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 19. Cantor Dynamics

Abstract
The main goal of this chapter is the presentation of the Bratteli–Vershik model developed by R. Herman, I.F. Putnam and C.F. Skau in their remarkable paper [46].
In the first section, we recall definitions of dynamical concepts, that will be often used. The proofs of the results of this section can be found in any standard textbook on topological dynamics; see, for example, [59, 85, 86].
In the second section, we will specialize to Cantor minimal systems.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 20. Etale Equivalence Relations

Abstract
In the first section of this chapter, we will first recall the definition and the first properties of étale equivalence relations.We restrict our presentation to the notions we will need in the next chapters; for more details see, for example, [74, 78, 80]. In the second section, we recall the definitions of isomorphism and orbit equivalence of étale equivalence relations. In the second section, we define AF-equivalence relations, a rich but also tractable class of étale equivalence relations that we will classify up to isomorphism and up to orbit equivalence, respectively, in Section 20.5 and Chapter 22.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 21. The Absorption Theorem

Abstract
The absorption theorem is the main result in this chapter and is the key tool we will use to classify up to orbit equivalence minimal AF-equivalence relations and étale equivalence relations associated to minimal actions on the Cantor set of finitely generated abelian groups. This key result shows that a “small” extension of a minimal AF-equivalence relation is orbit equivalent to the original one.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 22. Orbit Equivalence of AF-Equivalence Relations

Abstract
In Definition 20.4.33, we introduced the invariant Dm(X,$$\mathcal{R}$$) for an étale equivalence relation $$\mathcal{R}$$ on a totally disconnected, compact Hausdorff space X, and showed in Proposition 20.4.40 that it is an orbit equivalence invariant. In this chapter, we will show that this invariant is complete for the class of AF equivalence relations. The classification up to orbit equivalence of minimal AF-equivalence relations will be a corollary of the following theorem from Putnam [78].
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 23. Orbit Equivalence of Minimal Actions of a Finitely Generated Abelian Group

Abstract
In measurable dynamics, the study of orbit equivalence, initiated by Dye [19], was developed by Krieger [56], Ornstein–Weiss [73] and Connes–Feldman–Weiss [13] among many others in the amenable case. The strategy of their proofs consisted of showing that any amenable measurable equivalence relation is orbit equivalent to a hyperfinite measurable equivalence relation and classifying these ones. In the nonsingular case, the complete invariant of orbit equivalence is an ergodic flow, the so-called associated flow; see Krieger [56].
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 24. Orbit and Strong Orbit Realization for Minimal Homeomorphisms: Ormes’ Results

Abstract
In the first part of this chapter we will present Jewett–Krieger type realization results of an ergodic dynamical system by a Cantor minimal system in a prescribed orbit equivalence class. Nic Ormes proved them in his thesis and they are published in [71].
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms

### Chapter 25. Full Groups

Abstract
The notion of full group was introduced in 1959 by H. Dye in his study of orbit equivalence of measured dynamical systems [19] and [20].
In the first part of this chapter we will review the definition of full groups in the measurable case. We will then describe some of their properties. In the second part, we will present the different full groups associated to a topological dynamical system (on the Cantor set) and study their properties in comparison with the measurable case. Since their introduction in [39], the so-called topological full groups have been intensively studied and outstanding results obtained. As remarkable surveys on topological full groups and their properties have recently been written (see de Cornulier [14], Juschenko [53], and Matui [66]), we will review only in this section the properties of full groups.
Thierry Giordano, David Kerr, N. Christopher Phillips, Andrew Toms
Weitere Informationen


text:
It is basic fact of measure theory that there is no uniform measure on a countable set such as the set ${{\mathbb N}}$ of all natural numbers. However, there are many ways to measure size of subsets of ${{\mathbb N}}$. For instance, the set of even numbers ${2{\mathbb N}}$ should have ${1/2}$ of all the measure. With this philosophy, the precise definition of natural density appeared:

Definition 1 (Natural density) Let ${A\subset{\mathbb N}}$. Define the natural density of ${A}$ to be the number ${\displaystyle\lim_{n\rightarrow\infty}\frac{|[n]\cap A|}n}$, when the limit exists (and is undefined when the limit does not exist).

Among other good properties of the natural density, we quickly realize that ${d(A+n)=d(A)}$ for any ${n\in{\mathbb Z}}$ (where ${A+n:=\{x\in{\mathbb N}:x-n\in A\}}$). Thus ${A}$ is an additively invariant density over ${{\mathbb N}}$.
For some purposes, it turns out that it is convenient to have a density which is invariant under multiplication, thus the sets ${A}$ and ${rA}$ should have the same density for every ${r\in{\mathbb Q}}$ (where ${rA:=\{x\in{\mathbb N}:x/r\in A\}}$). We will see that such a density also exists. However, no density can be both invariant under addition and multiplication simultaneously (I say a little about this after Theorem 1 in my previous post).
A question raised by these observations is whether additively “large” sets must be multiplicatively “large” or vice versa. In this post we give some partial answers to this question (spoiler alert: the answer is usually no). In particular we will exhibit examples of sets in ${{\mathbb N}}$ that have opposite “size” regarding additive and multiplicative density.

— 1. Definitions and notation —

We start by making more precise definitions. As usual, for ${M\in{\mathbb N}}$ we denote ${[M]:=\{1,2,...,M\}}$. If ${x\in{\mathbb N}}$ and ${F\subset{\mathbb N}}$ we define ${xF:=\{xn:n\in F\}}$ and ${x+F:=\{x+n:n\in F\}}$.
We have the following

Definition 2 (Følner sequence)

• An additive Følner sequence is a sequence ${(F_n)}$ of finite subsets of ${{\mathbb N}}$ such that for all ${x\in{\mathbb N}}$ we have ${|(x+F_n)\cap F_n|/|F_n|\rightarrow1}$.
• A multiplicative Følner sequence is a sequence ${(F_n)}$ of finite subsets of ${{\mathbb N}}$ such that for all ${x\in{\mathbb N}}$ we have ${|(xF_n)\cap F_n|/|F_n|\rightarrow1}$.

As an example of additive Følner sequence take ${F_n=[n]}$. A more general example if ${F_n=[a_n,a_n+n]}$ for any sequence ${(a_n)}$ in ${{\mathbb N}}$ . An example of a multiplicative Følner sequence is the following:

$\displaystyle F_n=\big\{p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}\mid 0\leq e_1,e_2,\dots,e_n\leq n\big\}$

where ${p_1,p_2,\dots}$ are the prime numbers (we can take any arbitrary ordering of the prime numbers, as long as every prime appears in the sequence).
The following lemma (which follows easily from the definitions) gives more examples of Følner sequences.

Lemma 2 Let ${(F_n)}$ be a Følner sequence and let ${(x_n)}$ be a sequence taking values on ${{\mathbb N}}$. If ${(F_n)}$ is an additive Følner sequence, then ${(x_n+F_n)}$ is still an additive Følner sequence and if ${(F_n)}$ is a multiplicative Følner sequence, then ${(x_nF_n)}$ is still a multiplicative Følner sequence.

We can now define densities. It turns out that the family of sets for which the natural density is defined does not behave well with respect to set theoretical operators. Thus it is convenient to broaden the definition to allow any subset of ${{\mathbb N}}$. To do so, we simply take the ${\limsup}$ instead of the ${\lim}$.

Definition 3 (Density)

• Given a Følner sequence ${(F_n)}$ (additive or multiplicative) and a set ${A\subset{\mathbb N}}$, the upper density of ${A}$ with respect to ${(F_n)}$ is the number ${\displaystyle\limsup_{n\rightarrow\infty}\frac{|F_n\cap A|}{|F_n|}}$.
• The additive (resp. multiplicative) upper Banach density of a set ${A\subset{\mathbb N}}$ is the supremum over all additive (resp. multiplicative) Følner sequences of the upper density of ${A}$.
• Given a Følner sequence ${(F_n)}$ (additive or multiplicative) and a set ${A\subset{\mathbb N}}$, the lower density of ${A}$ with respect to ${(F_n)}$ is the number ${\displaystyle\liminf_{n\rightarrow\infty}\frac{|F_n\cap A|}{|F_n|}}$.

The following result follows from the fact that ${|F_n|\rightarrow\infty}$ as ${n\rightarrow\infty}$ for any Følner sequence.

Lemma 3 Let ${A\subset{\mathbb N}}$, let ${F\subset A}$ be a finite set and let ${B=A\setminus F}$. Then the density of ${B}$ is the same as the density of ${A}$ (upper or lower density with respect to a (additive or multiplicative) Følner sequence, natural density and upper Banach density).

While Følner sequences for a general class of semigroups were introduced by Følner, the multiplicatively invariant density on ${{\mathbb N}}$ was maybe studied for the first time by Bergelson in this paper.

— 2. Independence between additive and multiplicative densities —

In this section we answer (mostly in the negative) some precise reformulations of the question in the introduction, regarding the relation between the additive and multiplicative densities.
We start with an example that suggests a certain independence between the two notions.

Proposition 4 There exists a set ${A\subset{\mathbb N}}$ whose additive Banach upper density is ${0}$ and the lower density with respect to some multiplicative Følner sequence is ${1}$.

Proof: Let ${(F_n)}$ be some multiplicative Føner sequence and let ${M_n=\max F_n}$ so that ${F_n\subset[M_n]}$. Define the sequence ${(a_n)}$ of natural numbers by ${a_1=1}$ and for ${n>1}$ let ${a_n=2a_{n-1}M_n}$. Let ${\displaystyle A=\bigcup_{n=1}^\infty a_n[M_n]}$, we claim that it satisfies the proposition. Since ${(a_nF_n)}$ is a multiplicative Følner sequence by Lemma 2 and ${|A\cap a_nF_n|=|a_nF_n|=|F_n|}$ we conclude that the lower density of ${A}$ with respect to ${(a_nF_n)}$ is ${1}$.
Now for each ${N\in{\mathbb N}}$ let ${\displaystyle A_N=\bigcup_{n=N}^\infty a_n[M_n]}$. Note that ${A_N}$ is obtained from ${A}$ by removing a finite set, so by Lemma 3 the additive Banach upper density of ${A}$ is the same as that of ${A_N}$. On the other hand, the sets ${\{A_N-i,i=1,...,a_N\}}$ are pairwise disjoint, so for any additive Følner sequence we get that the upper density of ${A_N}$ is at most ${1/a_N}$. Since ${N}$ was arbitrary we conclude that the Banach upper density of ${A}$ is ${0}$ as desired. $\Box$
For the next result we need a lemma:

Lemma 5 Let ${P}$ be a set with ${0}$ additive upper density with respect to some fixed arbitrary Følner sequence. Then for every ${n\in{\mathbb N}}$ there exists some ${a\in{\mathbb N}}$ such that the interval ${[a,a+n]}$ is disjoint from ${P}$.

Proof: For each ${i\in[n]}$, the set ${P-i}$ has ${0}$ density, hence the finite union

$\displaystyle \bigcup_{i=0}^n(P-i)$

still has ${0}$ density and hence is not all of ${{\mathbb N}}$. Let ${a}$ be a number not in that union. Then for each ${i\in\{0,\dots,n\}}$ we have ${a\notin(P-i)}$ which is equivalent to ${a+i\notin P}$. We conclude that ${[a,a+n]}$ is disjoint from ${P}$ as desired. $\Box$

The next result is in some sense complementary to Proposition 4.

Proposition 6 There exists a set ${A\subset{\mathbb N}}$ such that ${A}$ has multiplicative Banach upper density ${0}$ but for some additive Følner sequence, the lower density of ${A}$ is ${1}$.

Proof: We define the sequences ${(a_n)}$ of natural numbers and ${(A_n)}$ of finite sets of ${{\mathbb N}}$, recursively by ${a_1=1}$, ${A_1=\{1\}}$ and for ${n>1}$ we let ${a_n>a_{n-1}}$ be such that ${[a_n,a_n+n]}$ is disjoint from ${\displaystyle \bigcup_{k=1}^\infty 2^kA_{n-1}}$ and we let ${A_n=A_{n-1}\cup [a_n,a_n+n]}$.
Observe that we can always choose such ${a_n}$ because the set ${\displaystyle \bigcup_{k=1}^\infty 2^kA_{n-1}}$ can be rewritten as ${\displaystyle \bigcup_{x\in A_{n-1}}xP}$ where ${P=\{2^k:k\in{\mathbb N}\}}$ has natural density ${0}$. Hence each of the sets ${xP}$ has natural density ${0}$ and thus also the finite union over ${A_{n-1}}$ has natural density ${0}$. By Lemma 5 we can choose ${a_n}$ as desired.
Let ${A=\bigcup A_n}$. It has lower density ${1}$ with respect to the additive Følner sequence ${([a_n,a_n+n])}$. Also note that the multiplicative shifts ${\{2^kA,k\in{\mathbb N}\}}$ are all disjoint, so ${A}$ has zero multiplicative density with respect to every multiplicative Følner sequence. $\Box$
Since the natural density implies more regularity to a set than just upper density, it is natural to wonder if the previous result still holds with the upper density with respect to some Følner sequence replaced with natural density. As an indication in this direction is the following:

Proposition 7 For every ${\epsilon>0}$ there is a set ${A\subset{\mathbb N}}$ of natural density at least ${1-\epsilon}$ and such that ${A}$ has multiplicative Banach upper density ${0}$.

Proof: Let ${k\in{\mathbb N}}$ and take ${A:={\mathbb N}\setminus\bigcup_{i=1}^\infty i^k{\mathbb N}}$ to be the set of ${k}$-th power free numbers. It is a classical fact that the natural density of ${A}$ is ${1/\zeta(k)}$ where ${\zeta}$ is the Riemann zeta function. On the other hand, the sets ${\{p^kA: p\text{ is prime}\}}$ are pairwise disjoint, therefore the upper density of ${A}$ with respect to any multiplicative Følner sequence is ${0}$ $\Box$
The next proposition is in the opposite flavor of the previous ones, in the sense that it establishes some relation between additive and multiplicative structure.

Proposition 8 If ${A\subset{\mathbb N}}$ is such that the natural density of ${A}$ is ${1}$, then there exists some multiplicative Følner sequence ${(F_n)}$ such that the upper density of ${A}$ with respect to ${(F_n)}$ is also ${1}$.

Proof: Note that for each ${k\in{\mathbb N}}$, the set ${A/k:=\{x\in{\mathbb N}:kx\in A\}}$ still has natural density ${1}$. Moreover, any finite collection of sets of natural density ${1}$ has non-empty intersection.
Let ${(G_n)}$ be an arbitrary multiplicative Følner sequence. For each ${n\in{\mathbb N}}$ let ${x_n}$ be in the intersection ${\bigcap_{k\in G_n}A/k}$. Then ${F_n:=x_nG_n\subset A}$. Since by lemma 2 ${(F_n)}$ is a multiplicative Følner sequence we are done. $\Box$
Observe that a set ${A\subset{\mathbb N}}$ has natural density ${1}$ if and only if its lower density with respect to the Følner sequence ${([n])}$ is ${1}$. Thus it is natural to try to weaken the hypothesis of the previous proposition, and also the conclusion. I don’t know the answer to the following question:

Question 9 Is it true that if ${A\subset{\mathbb N}}$ has upper density ${1}$ with respect to the additive Følner sequence ${F_n=[n]}$, then ${A}$ has positive upper density with respect to some multiplicative Følner sequence?

Another intriguing question is whether there exists a set ${A\subset{\mathbb N}}$ which has natural density strictly between ${0}$ and ${1}$ and multiplicative upper density also strictly between ${0}$ and ${1}$ for some Følner sequence. While there seems to be no reason why such set shouldn’t exist, I could not find an example.


text:
Symbol
Problem
$111$ 1.The sum of the roots of the quadratic equation $ax^{2}+bx+c=0is\dfrac {-b} {a}$ $2.$ The product of the roots of the quadratic equation $ax^{2}+bx+c=0is\dfrac {c} {a}$ To determine the quadratic equation given the sum and the product of the roots $use3$ $2-$ (the sum of the roots) $\right)$ $x+$ $1$ (the product of the roots) $s\right)=0$


text:
# Citation style error - Mendeley and LaTex [duplicate]

I have some citation errors using mendeley and latex (texmaker). I do not know how to explain the errors so I attached the code. Please run it and help if you can.

How to make that: in text - all the articles to appear "last name et al year" ??? in bibliography - all the authors to appear and the order of the names to be "first - last" ???

\documentclass[12pt,a4paper,twoside,openright]{book}
\usepackage[
backend=biber,
style=authoryear,
%sorting=none,
maxcitenames=1,
citestyle=authoryear]{biblatex}
\begin{document}
\textbf{ERROR In text}:\\

This is good: \cite{Chapman1964}\\

This is not good: \cite{Nie2007}, neither this: \cite{Nie2003}\\
Why do I have more than one name? \textit{\textbf{(1. I want all to be "last name et al." - how to do it?)}}\\

For bibliography errors:\\
\cite{Arrayago2015}\\
\cite{Bursi2005}\\

\textbf{ERROR In bibliography?\\}

1. Why some articles have all the authors and others just the first and "et. al" - see first two. \textit{\textbf{(2. How to modify this to be make all the authors appear in the bibliography?)}}\\

2. Why the first author is "last name - first name" and the others "first name last name"? \textit{\textbf{(3. What should I do make all the articles be "last - first name".)}}

\end{document}

the bibliography.bib file contains:

@article{Chapman1964,
author = {Chapman, JC and Balakrishnan, S},
journal = {The Structural Engineer},
number = {1},
pages = {369--383},
title = {{Experiments on composite beams}},
volume = {42},
year = {1964}
}

@article{Arrayago2015,
author = {Arrayago, I and Picci, F and Mirambell, E and Real, E},
doi = {10.1016/j.tws.2015.02.012},
journal = {Thin-Walled Structures},
pages = {96--107},
title = {{Interaction of bending and axial load for ferritic stainless steel RHS columns}},
volume = {91},
year = {2015}
}

@article{Bursi2005,
author = {Bursi, OS and Sun, FF and Postal, S},
doi = {10.1016/j.jcsr.2004.06.002},
journal = {Journal of Constructional Steel Research},
number = {1},
pages = {67--92},
title = {{Nonlinear analysis of steel concrete composite frames with full and partial shear connection subjected to seismic loads}},
volume = {61},
year = {2005}
}

@article{Nie2007,
author = {Nie, J and Cai, CS and Zhou, TR and Li, Y},
doi = {10.1061/(ASCE)0733-9445(2007)133:4(530)},
journal = {Journal of Structural Engineering},
number = {4},
pages = {530--540},
title = {{Experimental and Analytical Study of Prestressed Steel Concrete Composite Beams Considering Slip Effect}},
volume = {133},
year = {2007}
}

@article{Nie2003,
author = {Nie, J and Cai, CS},
doi = {10.1061/(ASCE)0733-9445(2003)129:4(495)},
journal = {Journal of Structural Engineering},
number = {April},
pages = {495--506},
title = {{Steel Concrete Composite Beams Considering Shear Slip Effects}},
volume = {129},
year = {2003}
}

Any help would be appreciated. Thank You!

• Your first complaint looks like something uniquelist=false and uniquename=false might be able to solve, see also Set limit to one author when using “et al.” in biblatex and Biblatex: Have only one author in citation. The second comes up quite often as well, so much so it is discussed in Guidelines for customizing biblatex styles, try \DeclareNameAlias{sortname}{last-first} or \DeclareNameAlias{sortname}{first-last}. – moewe Jun 22 '15 at 16:54
• Welcome! If the labels in you text are last name -- year style, then you need those labels in your bibliography. If the entries there start first name ... then how are people supposed to find the entry you are citing? – cfr Jun 22 '15 at 17:33
• Thank you both! I entered maxbibnames=9 and \DeclareNameAlias{sortname}{last-first} in the preamble and all the problems were solved! Thank you again! – Miculas13 Jun 24 '15 at 14:15
• @cfr the problem was that in bibliography the first author was "last name, first name" (so it was possible to find the entry I cited in the text) and 2nd, 3rd ... were "first name, last name". As I said in the previous comment adding \DeclareNameAlias{sortname}{last-first} in the preamble solved the problem! Thank you again! – Miculas13 Jun 24 '15 at 14:20
• Since your questions have essentially been covered before I'm voting to close as a duplicate of Set limit to one author when using “et al.” in biblatex (I had to choose, so I went with this one). – moewe Jun 24 '15 at 19:13


text:
Tuesday, January 16, 2018

Donald Knuth Turns 80 years and 6 days

Celebrating Donald Knuth's 80th birthday, or 80 years + 7 days birthday seems odd. Should we use powers of 2? Hmm- too few, just 32 and 64 really. And having a 32-year celebration for someone is unusual. How about numbers that end in 0 in base 8. 64 would be 100, 72 would  110, 80 would be 120 so AH- we would be celebrating! So lets Celebrate!

LANCE: One of us should blog about Don Knuth turning 80.

BILL: How about both of us, sep posts?

Lance had his post here. Now its my turn.

Donald Knuth was the first person (roughly- history is not as definite as mathematics) to use mathematics to analyse algorithms. This may seem like an obvious thing to do but that's easy to say in retrospect. And he never lost focus: He may have to use some hard math to analyze algorithms but his goal always was to analyze algorithms. He didn't get fascinated with some obscure aspect of math like, say, surreal numbers, and go write a book on it. Oh wait, he did (see here). But, for the most part everything he did was towards faster algorithm and faster typesetting.

In an early draft of a book review of  Companion \to the Papers of Donald Knuth I wrote at the end of it

Donald Knuth has been called the father of Theoretical Computer Science and hence his thoughts are worth knowing

I usually email my reviews to the author so they can make sure I didn't say anything stupid or in some very rare cases have a rebuttal. In Knuth's case I postal mailed it (ask your grandparents what that is) since he does not use email. He mailed back the hardcopy with some corrections in pencil. One of them was to cross out

father of theoretical computer science

and replace it with

father of algorithmic analysis.

I made the correction. That is how he views himself and it would be odd to argue the point.

As a tribute to him I have gathered up all of the book reviews  in my column of books by him (between 10 and 12 depending on how you count) and books clearly inspired by him (1 book- A=B) into one file which I point to  here

Wednesday, January 10, 2018

Donald Knuth Turns Eighty

We've kept this blog going long enough that we start repeating our celebrations. Ten years ago Bill celebrated Don Knuth's 70th Birthday and today Donald Knuth turns 80. While he celebrates in Piteå, Sweden with its less than 4.5 hours of daylight, we wish him a happy birthday from stateside.

Looking back in this blog, in 2015 I wrote about the history of the history of computing including this wonderful talk by Knuth, Let's Not Dumb Down the History of Computer Science.

Donald Knuth is known for many things, important algorithms, the brilliant book series The Art of Computer Programming, TeX, the many awards he's won and the award named after him. In my favorite story, back in the 70's when Knuth started working on Volume 4 (still in progress), he wanted a good name for those hard problems that Cook and Karp found. His candidates "Herculean", "Formidable" and "Arduous" didn't get much traction so he ran a contest which had some interesting suggestions before reluctantly going with the name "NP-complete" that came out of a group from MIT.

In his SIGACT News article that described the contest, Donald Knuth was so sure that these hard problems would remain hard, he puts everything on the line, offering anyone who could prove P = NP a live turkey. May Don Knuth and his turkey continue to celebrate many more birthdays.

Sunday, January 07, 2018

A new largest prime found!

A new largest KNOWN prime has been discovered and its 23 million digits long.

Nate Silver's website had an article about it (written by Oliver Roeder) here

An article about why people do this is  here

Lance posted about finding large primes in 2006 here

I'll just make some random comments

1) The prime is 277,232,917-1

2) The prime is not much bigger than the previous champion.

3) More generally, the graph (in Oliver Roeder's article) shows from 1600 to about 1951there was slow progress but since then there has been LOTS of progress. See the table in this article. I had wanted to say every year a new prime was found  but, alas, not that simple a pattern. Even so, lots of new records.

4) I"ll list the reasons given for why people do this and my comments on them.

a) Tradition! (Note to self- write a novelty song to the tune of Fiddler-on-the-roof's Tradition about why people work on various mathematical things)

b) For the by-product of the quest. This one does make sense and I am sure has driven and helped test out some research. Reminds me of the spinoffs from going to the moon (see here). Contrary to what I heard as a kid, the orange-powder-drink Tang was not a spinoff. But there were many others. Of course- would these spinoffs have happened anyway? Hard to know.

c) People collect rare and Beautiful items. I don't really see this one. Finding a large prime doesn't make  its yours, it belongs to the ages! And I don't think people get their names on the prime either. The only prime that has someone's name on it is the famous Grothendieck prime which is 57. Oh well. There are sets of primes with peoples names on them: Mersenne primes, Gaussian  primes (which are subsets of Gaussian integers so maybe shouldn't count), Eisenstein primes, and

d) For the glory! Maybe, but given how briefly people hold the record, fame is fleeting.

e) To test the hardware. This one I didn't know! I'll quote the article as to why primes are good for this
Why are prime programs used this way?  They are intensely CPU and bus bound.  They are relatively short, give an easily checked answer (when run on a known prime they should output true after their billions of calculations).  They can easily be run in the background while other "more important" tasks run, and they are usually easy to stop and restart.
f) To learn more about their distribution. The prime number theorem was conjectured from data. We have so many primes now that I wonder if a few more really help formulate conjectures

g) For the money. The first person to get a ten-million digit prime gets $100,000. The first person to get a one billion digit prime gets$250,000.  Wow! Except that the article must be a bit old since the \$100,000 prize was claimed in 2009 (see here). Still, theres that one billion digit prize out there!

5) Mersenne primes are of the form 2^n-1. It is known that n must be prime for 2^n-1 to be prime (this is not hard). There are much faster primality testing algorithms for Mersenne primes than arb primes. But see next item.

6) While writing this blog post I looked up non-mersenne primes. It seems like the largest one is

10223*2^31172165 + 1 and was discovered in 2016.

But of more interest- there is no Wikipedia page on non-Mersenne primes, there are some outdated pages that don't have the most recent information. As the kids say, its not a thing.

8) I'll add one more reason why people work on this, but its more of a tautology: People work on finding large primes because they can!. By contrast, finding VDW numbers is hard and likely to not make much progress.

9) I think that the most reason advances have come from computing power and not number theory. (if this is incorrect let me know with a polite comment)

10) Have their been spinoffs in either number theory OR computing power lately?

11) I wonder if there will come a point where progress gets hard again and the graph of largest known primes flattens out. I tend to think yes, but hard to say when.

Friday, January 05, 2018

Which of these Math acronyms are well known?

The last time I taught Grad Ramsey Theory there were very good math grads and ugrads in it. They used some acronyms - some I knew, some I didn't know (but know now).  I am sure some are well known and some are now. I don't know which is which. Here is the list and comments

WLOG- Without Loss of Generality. This one I know and it seems well know-- When Googled the first page is all this definition. (Maybe I shouldn't use the term Googled''- I've heard that brand names don't like it when they become generic terms like `Googled'. Kleenex, Photoshop, Xerox had this fate. Their is a word for it- genericide)

ITOT- It turns out that. An Applied Math Prof used this in a course I had in 1977. I have not seen it used since then. I don't even use it.

BWOC- By Way of Contradiction. I thought this was better known. When I google it I got to this page which tells me it stands for:

Big Wolf on Campus (TV Show)

By Weight of Cement (Oil and Gas industry)

Big Women on Campus (GOOD- the counterpart to BMOC)

By Way of  Contradiction (Given the other items on the list I'm surprised it made the cut)

Bob Wayne's Oil company

FTSOC- For the Sake of Contradiction. NOT, as Google told me, Fuck this Shit O'Clock (reminds me of when I use FML for Formula and the class tells me its means Fuck My Life)

WTS- This was a new one for me. It took a while to get it from context but it was Want to Show. Google gives Women in Transportation.

NTS- Need to show. Also a radio station and the National Traffic System.

I think the only one of these that is standard is WLOG.  The rest I think could be useful. But I ask you- are any of these standard? Are there ones that are standard that I missed? Of course, the great thing about standards is that there are so many of them.