text:
# Largest integer factored by Shor's algorithm?

I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody have an idea about this?

• See here. (not enough reputation to add as a comment) – Lying Dancer Jun 5 '18 at 9:07
• Just a heads up: there are more ways to factor with a quantum computer than Shor's, you might want to extend your question to ask both "the largest integer factored with Shor's" and "the largest integer factored". – Ruben De Smet Jun 5 '18 at 9:48

wondering what the largest integer is which they were able to factor with a small quantum computer

## Stunts

Before the present answer, the largest claim for quantum-related factoring seems to have been 4088459=2017×2027, by Avinash Dash, Deepankar Sarmah, Bikash K. Behera, and Prasanta K. Panigrahi, in [DSBP2018] Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer (arXiv:1805.10478, 2018) using 2 qubits (per their measure) of IBM quantum processors with 5-qubit and 16-qubit.

That's a pure stunt without application to cryptography, brought to a higher degree than in earlier work of Nikesh S. Dattani and Nathaniel Bryans, Quantum factorization of 56153 with only 4 qubits (arXiv:1411.6758, 2014) "factoring" e.g. 56153=233×241. The method applies only to a very narrow class of integers (those product of integers differing only by 2 bits, perhaps with some other constraints). 4088459 and 56153 are determined to fit the method.

The above "factorizations" extend, without requiring any experimental improvement, the earlier record of 143=11×13 by Nanyang Xu, Jing Zhu, Dawei Lu, Xianyi Zhou, Xinhua Peng, and Jiangfeng Du in Quantum Factorization of 143 on a Dipolar-Coupling Nuclear Magnetic Resonance System (Physical Review Letters, 2012). Their technique factors an integer product of two odd exactly-4-bit integers (thus with two unknown bits per factor). The scarcity of primes in range [8,15] makes 143 the only product of two distinct primes that the technique can factor. Their experimental setup iteratively minimizes a function with a 2-bit input.

An experimental improvement to 3-bit input, with application to 551=19×29, is claimed by Soham Pal, Saranyo Moitra, V. S. Anjusha, Anil Kumar, and T. S. Mahesh's Hybrid scheme for factorization: Factoring 551 using a 3-qubit NMR quantum adiabatic processor (arXiv:1611.00998, 2016). The authors acknowledge that the technique probably can't factor some larger 10-bit integers. The number factored depends on the molecule (dibromofluoromethane) used.

Zhaokai Li, Nikesh S. Dattani, Xi Chen, Xiaomei Liu, Hengyan Wang, Richard Tanburn, Hongwei Chen, Xinhua Peng, Jiangfeng Du's High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spinsystem: Application to the experimental factorization of 291311(arXiv:1706.08061, 2017) tackle 291311=523×557 using a different molecule ($$^3C$$-labeled diethyl-fluoromalonate).

Breaking news: I hereby claim a new stunt record. I change the last line of equation (2) in [DSBP2018] from $$p_i=q_i=1;\ i\in\{5,6,7,8,9\}$$ to $$p_i=q_i=1;\ i\in\{5,6,\dots,87\}$$, and the very same quantum experiment yields the "factorization" of the 178-bit biprime 383123885216472214589586724601136274484797633168671371=618970019642690137449562081×618970019642690137449562091, or otherwise said that $$2^{178}-(13\times2^{91})+651=(2^{89}-21)\times(2^{89}-31)$$.

For something non-stunt, defined as aiming to factor a wide fraction of arbitrary composites up to some limit, the record¹ may be Raouf Dridi and Hedayat Alghassi's Prime factorization using quantum annealing and computational algebraic geometry (in Nature scientific reports, 2017) factoring up to 223357=401×557 using the D-Wave 2000Q (an adiabatic quantum computer). A year later, the debate was still raging about the size of the true quantum computer that it could emulate.

## CAUTION - All the above is practically pointless!

None of the above techniques implement Shor's algorithm. They express factorization as a combinatorial minimization problem, solved using a variant of Grover's algorithm or adiabatic quantum computing. There is no argument for hope that these approaches could scale to factorization of integers of cryptographic interest.

## Shor's algorithm on quantum computers

We must separately consider the title's question:

Largest integer factored by Shor's algorithm?

I'm not aware of anything above 21=3×7 claimed by Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L. O'Brien in Experimental realisation of Shor's quantum factoring algorithm using qubit recycling (Nature Photonics, 2012).

This beats 15=3×5 first obtained by Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang in Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (Nature, 2001), then several others.

However it is debatable if these are really factoring, or rather confirming a known factorization. John A. Smolin, Graeme Smith and Alexander Vargo in Oversimplifying quantum factoring (Nature, 2013, formerly arXiv:1301.7007 with a different title) go as far as:

(there is) danger in ‘compiled’ demonstrations of Shor's algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice.

## Update (Sept 2020)

More stunts factorizations have appeared (see my critic), but the one in this answer remains the true (if under-reported) champion in this dubious category.

The progress on experimental non-stunt implementations seems to have stopped, both for combinatorial approaches using quantum adiabatic computers² and Schoor's algorithm. We do better understand the limitations of current hardware: Mirko Amico, Zain H. Salee, and Muir Kumph's Experimental study of Shor’s factoring algorithm using the IBM Q Experience (in physical review A, July 2019) conclude their work "fails to factor N=35". Experimental quantum computing currently prefers to focus not on beating classical computers at existing problems, but rather on finding problems where that happens beyond simulation of quantum computers.

An interesting new line of work makes mental experiments in factorization on hypothetical quantum computers: see Craig Gidney, Martin Ekerå's How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (arXiv:1905.09749, Dec 2019).

¹ Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Sabre Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 2018) "present how to factorize" 376289=571×659, but I was pointed that it is not an experimental result, sorry for having been careless.

² A close call was Baonan Wang, Feng Hu, Haonan Yao and Chao Wang's Prime factorization algorithm based on parameter optimization of Ising model (Scientic letter, April 2020) which claims a new combinatorial method factoring all integers to 10000, and in the stunt category 1028171=1009×1019, but got eliminated from both lists because that's on a simulation of a D-Wave quantum computer.

• How do you conclude factoring by Hamiltonian optimization is a variant of Grover's algorithm? And why is the factorization of 4088459 any more or less of a stunt than factorization of 143 by essentially the same method? – Squeamish Ossifrage Jun 5 '18 at 13:15
• @SqueamishOssifrage: First, I confess I'm far out of my comfort zone. I base my "variant of Grover's algorithm" on "our work makes use of the generalized Grover’s algorithm" in the abstract for the first paper I cite, and my understanding that in the first two papers factorization is essentially finding unknown bits (like 4 or so) that solve a combinatorial problem, which is similar to what Grover’s algorithm does. I base my "stunt" on the small number of bits involved in this minimization, which restricts to special-form integers. – fgrieu Jun 5 '18 at 13:24
• The classical reduction step depends on the form of the integer only to make it realizable in a prescribed concrete number of qubits, but the asymptotic growth is still polylogarithmic in $n$. The form of the integer may seem to be relevant in some cases because the relations obtained by reducing the binary multiplication are common to multiple integers with different solutions for the bits of the factors. The open question is how the quantum annealing step grows in cost with the number of bits. – Squeamish Ossifrage Jun 5 '18 at 13:33
• All of this is to say: The simplifications done classically (reducing the relations between bits of factors and product), compiling a fixed bases to quantum circuits) were needed to fit the computation into numbers of qubits we have available now. They are not necessary if it is possible to scale up the quantum circuits or quantum annealers to thousands of qubits. The limit is in the number of qubits, not the factoring or period-finding method. Will the superpolynomial costs of classical factoring or discrete log algorithms correspond to superpolynomial costs in scaling to many qubits? Maybe! – Squeamish Ossifrage Jun 5 '18 at 13:57
• @fgrieu 376289 was not actually factored in the first "non-stunt" paper you mention. They said in the abstract that they "show how to do it" which is misleading in my opinion because they actually "show how to" factor even RSA-4096 strictly speaking. At the end of the paper, they said that they were unable to factor 376289 because there was not enough qubits on the D-Wave machine. The record is still under 300000 in my opinion. – user1271772 May 10 '20 at 18:18

According to L. Zyga et al, N. Dattani and N. Bryans factored $56\,153 = 233 \cdot 241$ in November 2014, using a 4-qubit minimization (adiabatic quantum computation?) algorithm. Researchers believe that the method could be extended to factor $291\,311$. As of that time, the largest factorization achieved by Shor's algorithm was $21 = 3 \cdot 7$, and even that relied on prior knowledge of the answer.


text:
This study considers potential policy responses to the still very high levels of exposure to arsenic (As) caused by drinking water from shallow tubewells in rural Bangladesh. It examines a survey of 4,109 households in 76 villages of Araihazar upazila conducted two years after a national testing campaign swept through the area. The area is adjacent to the region where a long-term study was initiated in 2000 and where households are periodically reminded of health risks associated with well-water elevated in As. Results confirm that testing spurs switching away from unsafe wells, although the 27% fraction who switched was only about half of that in the long-term study area. By village, the fraction of households that switched varied with the availability of safe wells and the distance from the long-term study area. Lacking follow-up testing, two years only after the campaign 21% of households did not know the status of their well and 21% of households with an unsafe well that switched did so to an untested well. Well testing is again urgently needed in Bangladesh and should be paired with better ways to raise awareness and the installation of additional deep community wells.

## INTRODUCTION

The scale of the groundwater arsenic (As) problem in Bangladesh was recognized in the mid-1990s but mitigation of this public health crisis has stagnated. The first representative national survey showed that a population of 57 million was exposed in 2000 to levels up to a hundred times the World Health Organization guideline of 10 μg/L for As in drinking water (BGS/DPHE 2001; WHO 2011). Two national drinking-water surveys conducted since indicate a decline in the population exposed relative to the same guideline from 52 million in 2009 to 40 million in 2013, which is still an enormous number (BBS/UNICEF 2011, 2015). Relative to the outdated Bangladesh drinking water standard of 50 μg/L, the corresponding decline in the exposed population over the same period has been from an initial 35 to 22 and 20 million, respectively.

Epidemiological studies conducted in Bangladesh over the past two decades have linked a range of illnesses to As exposure from drinking well-water, including cardio-vascular disease and cancers of the lung, liver, and bladder in adults, and reduced intellectual and motor function in children (Smith et al. 2000; Wasserman et al. 2004; Sohel et al. 2009; Argos et al. 2010; Chen et al. 2011). On the basis of these studies, Flanagan et al. (2012) calculated an As-related mortality rate of one in every 18 adults over the next 20 years in Bangladesh associated with US$13 billion in economic losses, to which Pitt et al. (2015) add an estimated 9% reduction in household income associated with each As-exposed income earner across his or her lifetime. The task of further reducing the exposure to As in rural Bangladesh through new safe sources is enormous yet progress clearly is possible. Flanagan et al. (2012) report that investing US$11 per capita in mostly deep community wells lowered the exposure of a large population in the highly affected district of Comilla. In the less severely affected area of Araihazar upazila, a sub-district 20 km east of Dhaka, community wells reaching low-As aquifers at intermediate depths have provided low-As water to the surrounding populations for over a decade for an initial investment closer to US$1 per capita (van Geen et al. 2003a, 2007). Community wells for the 40 million villagers still exposed to As >10 μg/L nationally would therefore require investment in the range of US$40–440 million, less than one-tenth the cost of no action of over US$10 billion. Such an investment could double the already large number of deep community wells installed across the country over the past decade (DPHE/JICA 2009; Ravenscroft et al. 2014). Installing more community wells alone will not be sufficient to further reducing As exposure, however. Surveys conducted after blanket well-testing under the government's Bangladesh Arsenic Mitigation and Water Supply Program (BAMWSP) that ended in 2005 indicate a surprisingly large number of new installations of private wells that have remained largely untested (Ahmed et al. 2006; Opar et al. 2007; WASH 2008; George et al. 2012a; van Geen et al. 2014). For deep community wells to have the desired impact on household decisions, villagers must know if the wells that they own are safe or unsafe, given that fetching water from their well typically requires less effort than walking to a community well (Madajewicz et al. 2007). An additional benefit of testing wells is that, lacking a deep community well, households in many villages currently using an unsafe well have the option of walking to tested, safe neighboring wells to collect water (van Geen et al. 2002; George et al. 2012b). These nearby switching options have little or no financial cost but can be hampered by social barriers (Johnston et al. 2014). The cost of blanket testing approximately 10 million wells in the affected portions of the country would be on the order of U$20 million if a durable placard with the test result is provided (van Geen et al. 2014). The additional cost of maintenance testing to keep up with the replacement of 10% of wells annually would be about US\$2 million/year.

To inform policy responses, the present study focuses on learning from the initial impacts the BAMWSP testing campaign had on household reactions to As more than a decade ago. The findings are based on a household survey conducted in 76 villages in 2005, two years after testers hired under BAMWSP covered the study area using field kits. The aggregate switching in this area has previously been reported (Ahmed et al. 2006; Balasubramanya et al. 2014) but the impact of testing on household reactions was not interpreted geographically to the extent it is here. New features of the study include recording the location and As status of wells that households switched to and switching from untested wells. The study highlights the importance of raising awareness by relating household responses in the surveyed area to that of an adjacent region where, since 2000, households have been periodically reminded of the health risks associated with well-water elevated under the Health Effects of Arsenic Longitudinal Study (HEALS) described by Ahsan et al. (2006).

## METHODS

### Data collection

The household survey was conducted in Araihazar upazila between March and June 2005 (Figure 1) following approval from the Columbia University IRB. Growing rice and other crops is the traditional activity in this area about 20 km east of Dhaka (Figure 2), but textile and other industries have been developing rapidly. By 2003, essentially all the wells in the upazila had been tested for As by BAMWSP using a reasonably accurate field kit as part of a blanket national survey (van Geen et al. 2005). Each well was painted red (or painted green) if the field kit's test result was over (at or below) the national standard for drinking water in Bangladesh of 50 μg/L As.
Figure 1

Timeline of interventions and surveys conducted in Araihazar. Within the area considered in this study, this includes testing of wells conducted under BAMWSP (grey line) and the present response survey (black line). Also shown is the timing of testing and sampling activities conducted within the HEALS area. The text refers to response survey data of Chen et al. (2007) collected as part of the follow-up urine collection (black).

Figure 1

Timeline of interventions and surveys conducted in Araihazar. Within the area considered in this study, this includes testing of wells conducted under BAMWSP (grey line) and the present response survey (black line). Also shown is the timing of testing and sampling activities conducted within the HEALS area. The text refers to response survey data of Chen et al. (2007) collected as part of the follow-up urine collection (black).

Figure 2

Map of Araihazar upazila showing as pie diagrams the location of the 76 villages surveyed in 2005. Each pie diagram indicates the well status reported by the household: safe (green), unsafe (red), or unknown (yellow). The position of individual wells in the HEALS study area is show as grey dots; the position of wells surveyed under this study as black dots. The HEALS clinic is located at the intersection between the two major roads through the area, which are shown as grey lines. The inset shows the location of Araihazar and the Dhaka metropolitan area in Bangladesh. Please refer to the online version of this paper to see this figure in color: http://dx.doi.org/10.2166/washdev.2017.136.

Figure 2

Map of Araihazar upazila showing as pie diagrams the location of the 76 villages surveyed in 2005. Each pie diagram indicates the well status reported by the household: safe (green), unsafe (red), or unknown (yellow). The position of individual wells in the HEALS study area is show as grey dots; the position of wells surveyed under this study as black dots. The HEALS clinic is located at the intersection between the two major roads through the area, which are shown as grey lines. The inset shows the location of Araihazar and the Dhaka metropolitan area in Bangladesh. Please refer to the online version of this paper to see this figure in color: http://dx.doi.org/10.2166/washdev.2017.136.

Within an adjacent portion of Araihazar upazila (Figure 2), Columbia University launched HEALS in 2000 by sampling 6,000 wells that were tested in the laboratory (van Geen et al. 2003b). This was followed by an education campaign at the village level that relied on skits, songs, and focus-group discussions to encourage households to switch to a low-As well (Madajewicz et al. 2007). Roughly one out of ten households within the HEALS area were also reminded of the risks of exposure to As when baseline urine samples were collected (Figure 1). Both the education campaign and the baseline urine collection preceded a response survey conducted in 2002–2004 within the HEALS area as part of a follow-up of urine collection. BAMWSP testing was paired with a national media campaign and the vast majority of households in the study area were therefore aware of the As issue. This does not mean all households were necessarily correct in their perception of the risks and potential solutions.

Using BAMWSP data, 76 out of a total 300 villages in Araihazar were selected for this study. Selection criteria included a target minimum of 10 wells, in order to exclude very small villages, a minimum of 50% unsafe wells, and a location outside the HEALS area (Figure 2). A subset of 63 villages meeting these criteria was selected using a random number generator. An additional 13 villages were selected based on their proximity to the HEALS clinic to set the stage for an expansion of the cohort study (Figure 2). In each village, the field team approached the owners of all wells that they could find and conducted a ∼20 min survey by asking the wife of the well-owner, or instead a close female relative, a total of 15 questions. The teams recorded the position of each well (within 5–10 m) using a handheld Global Positioning System (GPS) receiver and recorded whether the red or green paint that had been applied to the pumphead of the well by BAMWSP was still visible. GPS coordinates and survey responses were recorded in the field using ESRI ArcPad 6.02 software. Each respondent was asked to recall her well's As result as well as whether her household had switched its main source of drinking water between 2003 and 2005. Respondents were also asked about their years of formal education. For all of those households who had switched their drinking water source, the tubewell to which they had switched as their new primary drinking source was linked in the database. Water samples were collected in 2005 from wells whose status was unknown then. Laboratory results were communicated to households as part of a subsequent household survey in a subset of the villages discussed in the present study (Cheng et al. 2007; Balasubramanya et al. 2014).

To the extent this could be ascertained, the position and status of all 4,372 wells across 76 villages was recorded during the survey. The number of wells per village averaged 54 and ranged from eight to 206. This suggests a population per village ranging from ∼100 to ∼2,000 when applying the average of 11 users per well documented in the adjacent HEALS area (van Geen et al. 2002). To help explain well-switching decisions by households, the linear distance from each unsafe well to the nearest safe well was calculated using ArcView 3.2. In addition, for all households who had switched their drinking source, the linear distances to the wells to which they had switched were calculated. These distances do not reflect the often tortuous paths that villagers have to follow from a home to a well because of the various obstacles present, such as ponds or property boundaries. For analyzing village-level average switching rates, a central village location was calculated by averaging well coordinates for each village, then the distance from each central location to the nearest well sampled within the HEALS area was calculated.

### Statistics

Well-switching responses two years after the end of BAMWSP testing are first analyzed at the household level. We use village effects, within linear least-squares regressions, to avoid bias due to differences across villages in factors we do not observe that influence average switching levels for villages. Their inclusion yields a more robust measure, relying on variation within each village, of the impacts of well-As status and, thus, the impacts of well-As testing. The three dependent variables considered in different regressions are: whether a household switched wells at all; whether a household that did switch wells went to a safe well, an untested well or an unsafe well; and how far a household member travels beyond the nearest safe well, if the household switched to a different well. The explanatory variables that were measured at the household level include whether the status of a well was safe, unsafe or unknown, the number of years of formal education of the respondent, and the linear distance to the nearest safe well if the household's well was unsafe. Aggregations of household responses are subsequently analyzed at the village-level in an attempt to explain variations in the fraction who switched from unsafe wells within each village. For this purpose, the distance of the village to the nearest HEALS well is an additional explanatory variable as a proxy for awareness.

## RESULTS

In total, 4,356 respondents were interviewed at the 4,372 wells, as the owners of 16 of those wells could not be identified. Of these 4,356 wells, only the 95% that did not have a mechanical problem and therefore functioned at the time of the survey were considered for our analyses. The sample for analyses is further slightly reduced by considering only those 4,109 functioning wells for which household information concerning well status and well usage was recorded.

As previously reported (Ahmed et al. 2006), interviewed households believed that 30% (i.e. 1,252) of their wells were safe while 49% (2,003) were considered unsafe. For the remaining 21% (854) of the wells, owners did not know the status of their well with respect to As (Figure 3). Paint was no longer visible on 24% of the wells because it had flaked off the rusty pumpheads between 2003 and 2005. However, the perception of well status matched the color of any paint recorded by the enumerator in 98% of cases. As also previously reported, 27% of households who indicated in 2005 that their well had been tested and found to be unsafe in 2003 reported having switched to a different drinking-water source (Ahmed et al. 2006; Balasubramanya et al. 2014). Further analysis of the data reported hereon has not been presented previously.
Figure 3

Pie diagram showing the proportion of wells in the study area whose status reported by the households that own them was unsafe (red), unknown (yellow), and safe (green). The number of wells within each pie is listed. The overlying portions of each pie shows the proportion of households that switched to a well other than their own and whose status they reported. Only in the case of unsafe wells is the perceived status of the wells households switched to known and indicated using the same color coding as above. Please refer to the online version of this paper to see this figure in color: http://dx.doi.org/10.2166/washdev.2017.136.

Figure 3

Pie diagram showing the proportion of wells in the study area whose status reported by the households that own them was unsafe (red), unknown (yellow), and safe (green). The number of wells within each pie is listed. The overlying portions of each pie shows the proportion of households that switched to a well other than their own and whose status they reported. Only in the case of unsafe wells is the perceived status of the wells households switched to known and indicated using the same color coding as above. Please refer to the online version of this paper to see this figure in color: http://dx.doi.org/10.2166/washdev.2017.136.

### Comparison between switching from safe, untested and unsafe wells

The proportion of wells perceived by their owners to be unsafe varied from 0 to 83% across villages. There is no clear geographic pattern to this distribution, with some villages that contained >75% unsafe wells located within a few kilometers of villages that contained <25% unsafe wells (Figure 2). Eighty-five percent of wells of unknown status were installed after the BAMWSP well-testing campaign in Araihazar ended in 2003. The proportion of wells of unknown status within a village also varied widely from 4 to 46% across the study area, again without any clear geographic pattern.

For those households believing their well to be safe, only 2% reported having switched their water source. Compared also to the 27% of households that switched from unsafe wells, an intermediate share of 13% of households reported switching from wells of unknown status (Figure 3). Regression analysis (not shown) indicates that the differences between these switching rates are significant whether village fixed effects are included or not.

Perceived well status with respect to As was not the only determinant of well switching. The average distance to the nearest safe well in a village decreases with the proportion of safe wells within that village (Figure 4(a)). Geography has an impact on switching, as indicated by the relationship between the proportion of switching and the average distance to the nearest safe well (Figure 4(b)). Education of the interviewed household member also had an impact on switching. Across all unsafe wells, there was predictable variation in rates of switching as a function of both education and distance to the nearest safe well (Table 1). Years of formal education of the respondents ranged from 0 to 16 years, averaging four years, and distance to the nearest safe well varied widely (10–600 m) across the study area, averaging 69 m. A one-standard-deviation increase in years of formal education (4 1/4 years) raised the well-switching rates by 3.5% (in absolute terms, i.e. percent of the group, the convention we use for all percentage results), while a one-standard-deviation increase in the distance to the nearest safe well (82 m) decreased the well-switching rates by 8%.
Table 1

Results from two household-level regressions and one village-level regression to determine relation between probability of switching, education, distance to the nearest safe well, and distance to the HEALS area

Independent variables of household-level regressionProbability of switching from unsafe wellsIndependent variables of household-level regressionProbability for those who switch beyond nearest safe wellIndependent variables of village-level regressionProbability of switching from unsafe wells
Education (year) 0.008 (p < 0.001) Education (yr) 0.008 (0.11) Average education (yr) 0.039 (0.00)
Distance to nearest safe well (m) −0.001 (p < 0.001) Distance to nearest safe well (m) −0.024 (p < 0.001) Distance to nearest safe well (m) −0.001 (0.01)
Log (distance to HEALS) −0.058 (0.01)
Constant 0.68 (0.00)
2003 467 76
Adjusted r2 0.22 Adjusted r2 0.11 Adjusted r2 0.28
Village effects included as controls for village differences in factors not observed  Village effects included as controls for village differences in factors not observed  F Statistic
Prob > F
F (3, 72) = 10.7
0.0000
Independent variables of household-level regressionProbability of switching from unsafe wellsIndependent variables of household-level regressionProbability for those who switch beyond nearest safe wellIndependent variables of village-level regressionProbability of switching from unsafe wells
Education (year) 0.008 (p < 0.001) Education (yr) 0.008 (0.11) Average education (yr) 0.039 (0.00)
Distance to nearest safe well (m) −0.001 (p < 0.001) Distance to nearest safe well (m) −0.024 (p < 0.001) Distance to nearest safe well (m) −0.001 (0.01)
Log (distance to HEALS) −0.058 (0.01)
Constant 0.68 (0.00)
2003 467 76
Adjusted r2 0.22 Adjusted r2 0.11 Adjusted r2 0.28
Village effects included as controls for village differences in factors not observed  Village effects included as controls for village differences in factors not observed  F Statistic
Prob > F
F (3, 72) = 10.7
0.0000
Figure 4

(a) Relationship between the proportion of switching from unsafe wells in a village and the average distance from an unsafe well to a safe well in that village (p < 0.05). (b) Relationship between the average distance from an unsafe well to the nearest safe well and the proportion of safe wells in that village (p < 0.05).

Figure 4

(a) Relationship between the proportion of switching from unsafe wells in a village and the average distance from an unsafe well to a safe well in that village (p < 0.05). (b) Relationship between the average distance from an unsafe well to the nearest safe well and the proportion of safe wells in that village (p < 0.05).

### Comparison of switching to safe, untested and unsafe wells

The survey data include information about the type of well households switched to when moving away from unsafe wells and, therefore, provide additional information on the impact of testing. Of those 559 households who had switched away from As-unsafe wells, the type and location of the well to which they had switched was recorded for 467 (Figure 3). The majority of these (73%) switched to safe wells but significant proportions also went to untested (21%) and to unsafe wells (6%).

The location of the wells households switched to suggest that additional factors, including possibly social barriers, may have significantly affected well switching. More than half (63%) of the households who switched from unsafe wells switched to a well that was farther away than the nearest safe well. The additional distance ranged from 4 to 162 m and averaged 36 m. A regression suggests that the distance to safe water influenced whether any such effective barriers were sufficient to dissuade households from switching to the nearest safe well (Table 1). The probability of switching to a well further than the nearest safe well fell by 24% for an additional 10 m of distance to the nearest safe well. During a subsequent survey conducted in the region, our field staff noted that a considerable number of households reported knowing of nearby safe wells but also that the well owners did not allow them to draw water there. Distance to source, considered here a proxy for access and effort required to switch to a different well, clearly plays a key role in household choices about their water used for drinking and cooking but is not the only consideration. This is consistent with the modest proportion of the variance in household behavior that is explained by the factors that were explicitly considered (Table 1).

### The impact of reinforcement

In the household-level analyses, unattributed differences in rates of switching averaged at the village level were removed using village effects in the regressions in order to focus on the differences in behavior between households. In this section, factors measured at the village level are instead considered to examine why the proportions of switching away from unsafe wells range so widely between villages (Figure 4). Not switching could represent household preferences but also could indicate other constraints including awareness.

One constraint on switching from unsafe wells already inferred from the analysis at the household level is the availability of safe wells. This is proxied here at the village level by the averaged distance between an unsafe well and the nearest safe well. Another potential factor affecting well-switching is information from the HEALS area where awareness has been raised as a result of the cohort study (Chen et al. 2007). Proximity to the HEALS area could plausibly affect a household's awareness of the health risks from exposure to As outside the immediate area. That proximity is proxied here by using the village's distance to the nearest well within the HEALS area. In this village-level regression, we use the logarithm of the distance to give more weight to shorter distances given that additional distance is unlikely to matter at large distances. The results show that education, average distance to the nearest safe well, and log distance to the HEALS area all are statistically significant determinants of switching from an unsafe well (Table 1). Similar results are obtained using distance to the nearest HEALS well itself or whether that distance is above or below the median for distances of the study villages.

Our field staff reported that an ‘activist’ individual had put extraordinary effort into raising awareness of the As threat and mobilizing responses. For any regression specification, the activist village clearly stands out as a significant positive outlier in terms of the rate of well switching controlling for other factors. This may indicate that such reinforcement lowered social barriers to switching.

## DISCUSSION

### The growing number of untested wells

No national or regional blanket testing has been attempted in Bangladesh since 2003 whereas households have continued to install additional wells and replace old wells (Opar et al. 2007). In Araihazar in 2012–2013, the As status of half of the wells was unknown, both because the total number of wells doubled since 2001 and because wells are abandoned at an average rate of 7% per year (van Geen et al. 2014). The proportion of untested wells has grown rapidly not only in Arahaizar. A country-wide survey of over 19,000 households showed that the proportion of untested wells in 35 As-affected upazilas distributed throughout Bangladesh grew by 2009 to an average of 39% (DPHE/JICA 2009). A more recent blanket survey of over 6,700 households within 26 villages in Singar upazila found that 56% of the wells were untested in 2009–2010 (George et al. 2012b).

### Opportunities for further reductions in exposure

A new national well-testing campaign has been under discussion in Bangladesh, a decade after the only previous blanket testing campaign ended. Our response data from Araihazar allows us to estimate the potential exposure reductions from renewed testing. We start from average concentrations of 16 and 167 μg/L As, respectively, measured in wells of the adjacent HEALS area classified as safe and unsafe relative to the national standard (van Geen et al. 2003a). On this basis, the exposure by drinking from 1,252 safe wells and 2,003 unsafe wells in the present study area before BAMWSP testing averaged 109 μg/L. Sadly, the proportion of safe wells in newly installed wells has been shown to be no higher than in older wells and the average exposure from the remaining 854 wells of unknown status is therefore also 109 μg/L. After switching from unsafe wells according to the proportions recorded in 2005, the average exposure in the area was only lowered to 93 μg/L (for simplicity, this calculation ignores the smaller effects of switching from wells of unknown status and safe wells).

If well testing had continued and the status of all wells had remained known, a similar calculation shows that the average exposure would have declined further to 84 μg/L by eliminating wells of unknown status. Continued testing probably would also have raised awareness and reduced social barriers and could therefore plausibly have doubled the switching rate to that observed in the HEALS area, resulting in a further decline to an average of 59 μg/L, a little over half the initial exposure (Balasubramanya et al. 2014). Given the evidence that social barriers inhibit well switching and sharing, future interventions should place more emphasis on behavior-change techniques that can alter intentions and commitment strength (Miguel and Kremer 2004) and have proved effective at enhancing well-switching (Munshi & Myaux 2006; Inauen et al. 2013; Johnston et al. 2014).

Further reductions in exposure that do not require water treatment could be achieved by installing additional deep community wells in affected areas of the country. A spatial calculation based on the distribution of wells in Araihazar has shown that the installation of about 2,000 deep community wells could have brought 90% of the population with an unsafe well to live within 100 m of a safe well. However, the siting of these deep community wells would have to be optimized to benefit the overall population (van Geen et al. 2015; Human Rights Watch 2016). The benefits of such an investment would be substantial in terms of exposure given that deep aquifers in Araihazar average 3 μg/L As (van Geen et al. 2003b).

## CONCLUSIONS

This survey conducted a few years after the only comprehensive campaign to test wells for As across Bangladesh provides evidence of the impact of this massive intervention. However, only about half as many as households switched away from unsafe wells when compared with a neighboring area where risks of exposure to As were periodically reinforced. The reduction in exposure was also limited by the installation of new wells that have remained largely untested. Lack of testing and reinforcement therefore seriously limit the reduction of exposure that is possible even without installing additional deep community wells.

## ACKNOWLEDGEMENTS

This study was supported in part by NIEHS grant P42 ES010349. We thank the team of Dhaka University students who tirelessly collected the household and well data. We thank Joseph Graziano for his support (LDEO contribution number 8105) of the project and comments on the manuscript.

## REFERENCES

Ahmed
M. F.
Ahuja
S.
Alauddin
M.
Hug
S. J.
Lloyd
J. R.
Pfaff
A.
Pichler
T.
Saltikov
C.
Stute
M.
van Geen
A.
2006
Ensuring safe drinking water in Bangladesh
.
Science
314
,
1687
1688
.
Ahsan
H.
Chen
Y.
Parvez
F.
Argos
M.
Hussain
I.
Momotaj
H.
Levy
D.
van Geen
A.
Howe
G.
Graziano
J.
2006
Health effects of arsenic longitudinal study (HEALS): description of a multidisciplinary epidemiologic investigation
.
J. Expo. Sci. Environ. Epidemiol.
16
,
191
205
.
Argos
M.
Kalra
T.
Rathouz
P. J.
Chen
Y.
Pierce
B.
Parvez
F.
Islam
T.
Ahmed
A.
Rakibuz-Zaman
M.
Hasan
R.
Sarwar
G.
Slavkovich
V.
van Geen
A.
Graziano
J.
Ahsan
H.
2010
A prospective cohort study of arsenic exposure from drinking water and all-cause and chronic disease mortality in Bangladesh
.
Lancet
376
,
252
258
.
BBS/UNICEF
2011
Bangladesh National Drinking Water Quality Survey of 2009
.
Bangladesh Bureau of Statistics and UNICEF
,
Dhaka
.
BBS/UNICEF
2015
Bangladesh Multiple Indicator Cluster Survey 2012–2013, Progotir Pathey: Final Report. Bangladesh Bureau of Statistics (BBS) and UNICEF
.
Bennear
L.
Tarozzi
A.
Pfaff
A.
Balasubramanya
S.
Ahmed
K. M.
van Geen
A.
2012
Impacts of a randomized controlled trial in arsenic risk communication on household water supply choices in Bangladesh
.
J. Environ. Econ. Manage.
65
,
225
240
.
BGS/DPHE (British Geological Survey, Dept. of Public Health Engineering)
2001
Arsenic contamination of groundwater in Bangladesh
. In:
British Geological Survey Technical Report WC/00/19
(
Kinniburgh
D. G.
Smedley
P. L.
, eds).
British Geological Survey
,
Keyworth
,
UK
.
Chen
Y.
van Geen
A.
Graziano
J.
Pfaff
A.
Madajewicz
M.
Parvez
F.
Hussain
I.
Cheng
Z.
Slavkovich
V.
Islam
T.
Ahsan
H.
2007
Reduction in urinary arsenic levels in response to arsenic mitigation in Araihazar, Bangladesh
.
Environ. Health Perspect.
115
,
917
923
.
Chen
Y.
Graziano
J. H.
Parvez
F.
Liu
M.
Slavkovich
V.
Kalra
T.
Argos
M.
Islam
T.
Ahmed
A.
Rakibuz-Zaman
M.
Hasan
R.
Levy
D.
van Geen
A.
Ahsan
A.
2011
Arsenic exposure from drinking water and cardiovascular disease mortality: a prospective cohort study in Bangladesh
.
Br. Med. J.
342
,
d243
.
Cheng
Z.
Zheng
Y.
Mortlock
R.
van Geen
A.
2007
Rapid multi-element analysis of groundwater by high-resolution inductively coupled plasma mass spectrometry
.
Anal. Bioanal. Chem.
379
,
513
518
.
DPHE/JICA
2009
Situation Analysis of Arsenic Mitigation
.
Department of Public Health Engineering, Government of Bangladesh
,
Dhaka
,
Bangladesh
and
Japan International Cooperation Agency
.
Flanagan
S. V.
Johnston
R. B.
Zheng
Y.
2012
Arsenic in tube well water in Bangladesh: health and economic impacts and implications for arsenic mitigation
.
Bull. World Health Organ.
90
,
839
846
.
George
C. M.
van Geen
A.
Slavkovich
V.
Singha
A.
Levy
D.
Islam
T.
Ahmed
K. M.
Moon-Howard
J.
Tarozzi
A.
Liu
X.
Factor-Litvak
P.
Graziano
J.
2012a
A cluster-based randomized controlled trial promoting community participation in arsenic mitigation efforts in Bangladesh
.
Environ. Health
11
,
41
.
George
C. M.
Graziano
J. H.
Mey
J. L.
van Geen
A.
2012b
Impact on arsenic exposure of a growing proportion of untested wells in Bangladesh
.
Environ. Health
11
,
7
.
Human Rights Watch
2016
Nepotism and Neglect: The Failing Response to Arsenic in the Drinking Water of Bangladesh's Rural Poor
. .
Johnston
R.
Hug
S. J.
Inauen
J.
Khan
N. I.
Mosler
J. H.
Yang
H.
2014
Enhancing arsenic mitigation in Bangladesh. Findings from institutional, psychological, and technical investigations
.
Sci. Total Environ.
488–489
,
477
483
.
Madajewicz
M.
Pfaff
A.
van Geen
A.
Graziano
J.
Hussein
I.
Momotaj
H.
Sylvi
R.
Ahsan
H.
2007
Can information alone both improve awareness and change behavior? Response to arsenic contamination of groundwater in Bangladesh
.
J. Dev. Econ.
84
,
731
754
.
Munshi
K.
Myaux
J.
2006
Social norms and fertility transition
.
J. Dev. Econ.
80
,
1
38
.
Opar
A.
Pfaff
A.
Seddique
A. A.
Ahmed
K. M.
Graziano
J. H.
van Geen
A.
2007
Responses of 6500 households to arsenic mitigation in Araihazar, Bangladesh
.
Health Place
13
,
164
172
.
Pitt
M. M.
Rosenzweig
M. R.
Hassan
N.
2015
Identifying the Cost of a Public Health Success: Arsenic Well Water Contamination and Productivity in Bangladesh
.
NBER Working Paper No. 21741
.
National Bureau of Economic Research
,
Cambridge, MA
,
USA
.
Ravenscroft
P.
Kabir
A.
Hakim
S. A. I.
Ibrahim
A. K. M.
Ghosh
S. K.
Rahman
M. S.
Akter
F.
Sattar
M. A.
2014
Effectiveness of public rural waterpoints in Bangladesh with special reference to arsenic mitigation
.
J. Water Sanit. Hyg. Dev.
4
,
545
562
.
Smith
A.
Lingas
E.
Rahman
M.
2000
Contamination of drinking-water by arsenic in Bangladesh: a public health emergency
.
Bull. World Health Organ.
78
,
1093
1103
.
Sohel
N.
Persson
L. A.
Rahman
M.
Streatfield
P. K.
Yunus
M.
Ekström
E. C.
Vahter
M.
2009
Arsenic in drinking water and adult mortality: a population-based cohort study in rural Bangladesh
.
Epidemiology
20
,
824
830
.
van Geen
A.
Ahsan
H.
Horneman
A. H.
Dhar
R. K.
Zheng
Y.
Hussain
I.
Ahmed
K. M.
Gelman
A.
Stute
M.
Simpson
H. J.
Wallace
S.
Small
C.
Parvez
F.
Slavkovich
V.
LoIacono
N. J.
Becker
M.
Cheng
Z.
Momotaj
H.
Shahnewaz
M.
Seddique
A. A.
Graziano
J. H.
2002
Promotion of well-switching to mitigate the current arsenic crisis in Bangladesh
.
Bull. World Health Organ.
81
,
732
737
.
van Geen
A.
Ahmed
K. M.
Seddique
A. A.
Shamsudduha
M.
2003a
Community wells to mitigate the current arsenic crisis in Bangladesh
.
Bull. World Health Organ.
82
,
632
638
.
van Geen
A.
Zheng
Y.
Versteeg
R.
Stute
M.
Horneman
A.
Dhar
R.
Steckler
M.
Gelman
A.
Small
C.
Ahsan
H.
Graziano
J.
Hussein
I.
Ahmed
K. M.
2003b
Spatial variability of arsenic in 6000 tube wells in a 25 km2 area of Bangladesh
.
Water Resour. Res.
39
,
1140
.
van Geen
A.
Cheng
Z.
Seddique
A. A.
Hoque
M. A.
Gelman
A.
Graziano
J. H.
Ahsan
H.
Parvez
F.
Ahmed
K. M.
2005
Reliability of a commercial kit to test groundwater for arsenic in Bangladesh
.
Environ. Sci. Technol.
39
,
299
303
.
van Geen
A.
Cheng
Z.
Jia
Q.
Seddique
A. A.
Rahman
M. W.
Rahman
M. M.
van Geen
A.
2007
Monitoring 51 deep community wells in Araihazar, Bangladesh, for up to 5 years: implications for arsenic mitigation
.
J. Environ. Sci. Health A
42
,
1729
1740
.
van Geen
A.
Ahmed
E. B.
Pitcher
L.
Mey
J. L.
Ahsan
H.
Graziano
J. H.
Ahmed
K. M.
2014
Comparison of two blanket surveys of arsenic in tubewells conducted 12 years apart in a 25 km2 area of Bangladesh
.
Sci. Total Environ.
488–489
,
484
492
.
van Geen
A.
Ahmed
K. M.
Ahmed
E. B.
Choudhurry
I.
Mozumder
M. R.
Bostick
B. C.
Mailloux
B. J.
2016
Inequitable allocation of deep community wells for reducing arsenic exposure in Bangladesh
.
Journal of Water, Sanitation and Hygiene for Development
6
,
142
150
.
WASH
2008
WASH Programme of BRAC: Towards Attaining the MDG Targets: Baseline Findings
.
BRAC
,
Dhaka
,
Bangladesh
.
Wasserman
G. A.
Liu
X.
Parvez
F.
Ahsan
H.
Factor-Litvak
P.
van Geen
A.
Cheng
Z.
Slavkovich
V.
Hussain
I.
Momotaj
H.
Graziano
J. H.
2004
Water arsenic exposure and children's intellectual function in Araihazar, Bangladesh
.
Environ. Health Perspect.
112
,
1329
1333
.
World Health Organization
2011
Guidelines for Drinking-Water Quality
, 4th edn.
World Health Organization
,
Geneva
,
Switzerland
.

format: plain


text:
# Truth-Functionally Complete Connectives

This is another “private communication” problem that I couldn’t find an obvious reduction for online.  I’ve used the holidays as an excuse to not put up a post so I could work on this problem, but even with the extra time, this problem has stumped me.

The problem: Truth-Functionally Complete Connectives.  This is problem LO10 in the appendix.

The description: Given a set U of variables, and a set C of well-formed Boolean expressions over U, is C truth-functionally complete?  In other words, can we find a finite set of unary and binary operators D = {θ1..θk} such that for each θi we can find an expression E in C, and a substitution s: U->{a,b} such that s(E) ≡ aθib (if θi is binary) or s(E) ≡ θia (if θi is unary)?

Example: So, “Truth-Functionally Complete” means that you can use the operations in D to generate all possible truth tables.  So some possible candidates for D are {AND, NOT} or just {NAND}.

So, if U = {x,y} and C = {~x, x∧y}, then I can just choose D to be {NOT, AND} and use the obvious substitution.  I think the hard part here is that the problem asks if such a D exists- I think the substitutions are probably always straightforward, once you get the functionally complete set D that gives you the best mapping..

Reduction: As I said above, this is a “Private Communication” problem, and so after a lot of searching, I found this paper by Statman, which I’m honestly am not even sure is the correct one. It at least talks about substitutions and deterministic polynomial time algorithms and things, but it very quickly goes into advanced Mathematical Logic that I wasn’t able to follow.  If someone out there knows more about this than I do and wants to chime in, let me know!

Edited Jan 22, 2020: Thanks to Thinh Nguyen for the help in coming up with the idea for the reduction- please check it out in the comments!

Difficulty: 10.  This is why we have the level 10 difficulty- for problems I can’t even follow.

### 10 responses to “Truth-Functionally Complete Connectives”

1. For a set $E$ of Boolean wff (well-formed formulae) to be (truth table) functionally complete, two elementary formulae, namely $\lnot a$ and $a \land b$ needs to be substitution-realizable from $E$.

So, we reduce from 3-set Splitting which is NP-complete according to Wikipedia (see link below). To (always) satisfy the realization of $\lnot a$, we always include a separate formula $\lnot u$. That means the variable $u$ is not used elsewhere.

For each element in the given instance, we add a variable $x_i$.

Now, for each $3$-set $\{x_1,x_2,x_3\}$ (plz note that I do not want to write the complicated indices $i_1$, $i_2$, $i_3$), we create a sub-formula: $x_1\land x_2\land x_3$.

Then, we create a big formula by ORing all the above sub-formulae. Finally, output two formulae, namely the tiny one $\lnot u$ and the big-OR one.

A solution to the truth-functionally complete problem needs to “cut” every 3-set into a-part and b-part. And, vice versa.

https://en.wikipedia.org/wiki/Set_splitting_problem

2. So, let me take this idea and flesh it out a little.
The reason we have a that’s separate from any element of S (the set of Set Splitting variables) is so that we can set to be . (And have it map to the expression).

will be “AND”. It will map to the giant expression (Basically forming a CNF-SAT instance of all of the sets we’re splitting). The formula will be equivalent to if we can split the variables into “a” and “b” variables.

But what I’m confused about is the final formula. If we’re just OR-ing together all of the clauses,isn’t is possible that we can get an equivalent expression with an illegal split? (Just setting that clause to false, since if other clauses are true, the whole express will come out to true anyway..)

• “If we’re just OR-ing together all of the clauses,isn’t is possible that we can get an equivalent expression with an illegal split? (Just setting that clause to false, since if other clauses are true, the whole express will come out to true anyway..)”

But the point here is: “to find a substitution s: U->{a,b} such that s(E) ≡ aθib (if θi is binary)”

We are not reducing from 3-SAT.

3. Right, so my question is:

Since we can take a true expression, and or it with anything else to still make a true expression, is it possible that there exist situations where we have an illegal split but still is logically equivalent to ?

So, like, I did the truth table and things like () or aren’t equivalent. There’s no other way (without negations) to be equivalent, right?

4. An invalid split never yields any formula equivalent to $latex a \land b$.

As in your example, if we are given a NO instance which does not have any valid splid. Then if someone comes up with an invalid split which gives us the formula $latex (a\land b)\lor b$, then he/she just fails convincing us that the instance is YES one.

5. Ok, I think I buy that.
Is it possible that in a NO instance we can come up with some _other_ set D of connectives that would work? (Since the problem only asks if one exists)

• Well, it is still possible to choose instead of .

But that is only possible when our given instance is disconnected into two connected components:

Only then, we can assign all literals in one connected component to a, the other connected component to b. Then (a AND a AND a) or (b AND b AND b) is just (a OR b).

But the NP-completeness proof assures us that the output instance is connected. We are safe.

• But what if D had like 9 operations in it? There are all kinds of crazy sets of operations that over the entire set, form a complete set of operations.

Maybe we can avoid that by saying that since for each we need to find an expression in E, and there are just 2 expressions in E, so any set D that has more than 2 elements is functionally equivalent to one with just 2 elements. And then we can show that there is just a small number of possible operations (exhaustively, if we have to), and show that for any set of 2 operations that’s complete, it has to split the variables.

Does that make sense?

• Yes, a detailed proof should be like that. And there are just a few cases to consider. Our second formula when substituted by a or b for each variable can only result in: a OR b, a AND b, (a AND b) OR b, (a AND b) OR a, (a AND b) OR a OR b, a, b. Not so many cases.


text:
# Uninstall Windows-agent¶

## Local uninstallation¶

Run the installer “agent_ru.msi” with administrator rights and choose the option Remove installation

Note

To remove the application it’s better to launch the same installer that was used for installation.

## Remote uninstallation¶

In a similar way the remote installer can be used to invoke mass or single uninstallation of agents.

For that you should upload the installation list that was previously saved or start another scanning of the system.

In the list of computers, choose those you want to remove and click the Remove button.

In some time after the removal we can start a new network scanning to make sure that the agents on the chosen workstations are removed and the icon next to the name of a workstation is “green”, which means that the system has the agent uninstalled.

## Silent uninstallation¶

Must be performed in the command line interface

Start - Programs - Standard - Command line, then click it with the right button and choose “Run with admin rights” and run the following command:

msiexec.exe /uninstall C:\windows\agent.msi /qn /norestart REBOOT=ReallySuppress

The agent installer (agent.msi) must be located in the folder «C:windows»


text:
통합검색

인기검색어

### 논문 상세보기

• 홈으로 이동
PROPERTIES SCUBA-2 850 ㎛ SOURCES AKARI NEP-DEEP FIELD
• 저자
Seo, Hyunjong
• 저널명
The Korean Astronomical Society
• 발행년도
2018
• 권호
V .51, N .3
• 원문보기
We carry out a study of Sub-Millimeter Galaxies (SMGs) in the AKARI NEP-Deep field using the James Clerk Maxwell Telescope (JCMT) SCUBA-2 $850{\mu}m$ source catalog, released as part of the SCUBA-2 Cosmology Legacy Survey (S2CLS) program. The SCUBA-2 $850{\mu}m$ map has a root mean square (rms) noise of $1.2mJy\;beam^{-1}$ and covers an area of $0.60degree^2$ . We find four SMGs which have counterparts to Herschel sources with spectroscopic redshifts in the literature. In addition, three dust obscured galaxies (DOGs) detected in Herschel bands are selected as a comparison sample. We derive IR luminosities of SMGs using the CIGALE code, which are similar to those of high redshift SMGs from previous studies. The contribution of AGN to the total IR luminosity in SMGs (2%-11%) is smaller than the lower limit for the one in DOGs (19%-35%), which is consistent with the expectation from the evolutionary scenario of massive galaxies. We search for SMGs in overdense regions as protocluster candidates and investigate four regions, including candidates around three DOGs. Finally, we argue that follow-up spectroscopic observation for the NEP-Deep field will provide crucial information to understand the role of SMGs in the evolution of massive galaxies


text:
# Substitution in partial differential equation

• I

## Main Question or Discussion Point

Hello everybody.
Consider
$$\frac{\partial}{\partial t}f(x) + ax\frac{\partial }{\partial x}f(x) = b x^2\frac{\partial^2}{\partial x^2}f(x)$$

They make the substitution $$y=ln(x)$$ and obtain
$$\frac{\partial}{\partial t}f(x) + a\frac{\partial }{\partial y}f(y) = b \frac{\partial^2}{\partial y^2}f(y)$$

My problem in second order term: what I would do is
$$bx^2\frac{\partial^2}{\partial x^2}f(x)=bx^2\frac{\partial }{\partial x}(\frac{\partial y}{\partial x}\frac{\partial }{\partial y} f(y))=bx^2\frac{\partial }{\partial x}(\frac{1}{x}\frac{\partial }{\partial y} f(y))=bx^2\frac{\partial y}{\partial x} \frac{\partial }{\partial y}(\frac{1}{x}\frac{\partial }{\partial y} f(y)) = bx\frac{\partial}{\partial y}(\frac{1}{x}\frac{\partial }{\partial y} f(y)) = b\frac{\partial^2}{\partial y^2}f(x) + bx(\frac{\partial }{\partial y}f(x))(\frac{\partial }{\partial y}\frac{1}{x})$$

So I obtain the term $$b\frac{\partial^2}{\partial y^2}f(x)$$ but I also have $$bx(\frac{\partial }{\partial y}f(x))(\frac{\partial }{\partial x}\frac{1}{x})$$
which is not 0 being
$$\frac{\partial }{\partial y}\frac{1}{x} = \frac{\partial }{\partial y}e^{-y} = -e^{-y}$$
so that I'm left with a term
$$bx(\frac{\partial }{\partial y}f(x))(\frac{\partial }{\partial x}\frac{1}{x}) = be^y(\frac{\partial}{\partial y}f(y))(-e^{-y})=-b\frac{\partial }{\partial y}f(y)$$
What is my mistake?
Thanks.

Related Differential Equations News on Phys.org
Chestermiller
Mentor
Hello everybody.
Consider
$$\frac{\partial}{\partial t}f(x) + ax\frac{\partial }{\partial x}f(x) = b x^2\frac{\partial^2}{\partial x^2}f(x)$$

They make the substitution $$y=ln(x)$$ and obtain
$$\frac{\partial}{\partial t}f(x) + a\frac{\partial }{\partial y}f(y) = b \frac{\partial^2}{\partial y^2}f(y)$$

My problem in second order term: what I would do is
$$bx^2\frac{\partial^2}{\partial x^2}f(x)=bx^2\frac{\partial }{\partial x}(\frac{\partial y}{\partial x}\frac{\partial }{\partial y} f(y))=bx^2\frac{\partial }{\partial x}(\frac{1}{x}\frac{\partial }{\partial y} f(y))=bx^2\frac{\partial y}{\partial x} \frac{\partial }{\partial y}(\frac{1}{x}\frac{\partial }{\partial y} f(y)) = bx\frac{\partial}{\partial y}(\frac{1}{x}\frac{\partial }{\partial y} f(y)) = b\frac{\partial^2}{\partial y^2}f(x) + bx(\frac{\partial }{\partial y}f(x))(\frac{\partial }{\partial y}\frac{1}{x})$$

So I obtain the term $$b\frac{\partial^2}{\partial y^2}f(x)$$ but I also have $$bx(\frac{\partial }{\partial y}f(x))(\frac{\partial }{\partial x}\frac{1}{x})$$
which is not 0 being
$$\frac{\partial }{\partial y}\frac{1}{x} = \frac{\partial }{\partial y}e^{-y} = -e^{-y}$$
so that I'm left with a term
$$bx(\frac{\partial }{\partial y}f(x))(\frac{\partial }{\partial x}\frac{1}{x}) = be^y(\frac{\partial}{\partial y}f(y))(-e^{-y})=-b\frac{\partial }{\partial y}f(y)$$
What is my mistake?
Thanks.
I think your reference is in error


text:
Friday the 13th

We all know that Friday the 13th is unlucky, but is it unlikely?

Contents

Year 2012

I plan to post this article during the second week of July, 2012. The Friday in this week is a Friday the 13th, the third we've had so far this year. There were also ones in January and April. That seems like a lot. How often do we have three Friday the 13ths in the first seven months of a year? Well, it's not all that often. It usually happens only once every 28 years. The next time will be the year 2040. But sometimes, around the turn of centuries, it happens twice in 12 years. I mention all this to establish that our calendar does not have a simple periodic behavior. By the way, not to worry, after this week, it will be 14 months until the next Friday the 13th, in September, 2013.

Friday the 13th

Which brings us to the central topic of this post:

• What is the probability that the 13th of a month falls on a Friday?

An obvious response is

• Easy question, the probability is 1/7.

After all, there are seven days in a week and the 13th of a month is equally likely to fall on any one of them. Well, as we shall see, that's close, but not exactly right.

Calendars and Leap Years

Leap years make our calendar a nontrivial mathematical object. The leap year rule can be implemented by this anonymous function.

leapyear = @(y) mod(y,4)==0 & mod(y,100)~=0 | mod(y,400)==0;

This says that leap years happen every four years, except the turn of a century not divisible by 400 is skipped. Try a few year numbers.

y = [2012 2013 2000 2100]';
disp([y leapyear(y)])

        2012           1
2013           0
2000           1
2100           0

So, this year is a leap year, next year is not, 2000 was a leap year, 2100 is not.

The leap year rule implies that our calendar has a period of 400 years. The calendar from 1601 to 2000 is being reused from 2001 to 2400. (Except the Gregorian calendar had not been invented in 1601, so I'm talking about the calendar that would have been used back then if they could have used today's calendar, but never mind.)

In a 400 year period, there are 97 leap years, 4800 months, 20871 weeks, and 146097 days. So the average number of days in a calendar year is not 365.25, but

format short
dpy = 365+97/400

dpy =

365.2425

We can compute the probability that the 13th of a month is a Friday by counting how many times that happens in 4800 months. The correct probability is then that count divided by 4800. Since 4800 is not divisible by 7, the probability does not reduce to 1/7.

Clock

MATLAB has a number of functions for doing computations involving calendars and dates. Many of these functions are in the MATLAB Toolbox, but some of the more specialized ones are in the Finance Toolbox. We encountered a few of these functions in my blog about biorhythms. The basis for all the functions is clock, which reads the system's clock and returns a 6-element vector

  [year, month, date, hour, minute, seconds]

The first five elements have integer values. The sixth element has a fractional part whose accuracy depends upon the computer's internal clock. Here is the output generated when I publish this blog.

c = clock;
fprintf('clock = [ %4d %4d %5d %5d %5d %8.3f ]\n',c)

clock = [ 2012    7     5    11    53   14.258 ]

Datenum

The datenum function facilitates computations involving calendars by collapsing the clock vector into one value, the serial date number. This value is the number of days, and fractions of a day, since a reference time 20 centuries ago when clock would have been all zeros. Here are a couple of examples of the use of datenum. If you run this code yourself, your results should be different.

t = now;
fprintf('current_date_number = %10.3f\n',t)
date_string = datestr(t)
tday = fix(t)
tday_string = datestr(tday)
[week_day,week_day_name] = weekday(tday)

current_date_number = 735055.495

date_string =

05-Jul-2012 11:53:14

tday =

735055

tday_string =

05-Jul-2012

week_day =

5

week_day_name =

Thu

Calendar number

The calendar for any year is determined by two pieces of information, the weekday of January 1st and whether or not the year is a leap year. So we need only 14 calendars. We could number all possible calendars, with the units digit specifying the starting week day and the tens digits indicating leap years. The 14 numbers would be [1:7 11:17].

calendar_number = @(y) weekday(datenum(y,1,1)) + 10*leapyear(y);

If the calendar industry used this numbering scheme, here are the calendars you would need for the next 21 years.

y = (2012:2032)';
disp([y calendar_number(y)])

        2012          11
2013           3
2014           4
2015           5
2016          16
2017           1
2018           2
2019           3
2020          14
2021           6
2022           7
2023           1
2024          12
2025           4
2026           5
2027           6
2028          17
2029           2
2030           3
2031           4
2032          15

Friday the 13th is likely

We are now ready to use the weekday function to count the number of times in a 400-year calendar cycle that the 13th of a month occurs on each of the various days of the week.

c = zeros(1,7);
for y = 1601:2000
for m = 1:12
d = datenum([y,m,13]);
w = weekday(d);
c(w) = c(w) + 1;
end
end
c

c =

687   685   685   687   684   688   684

A bar graph, with a line at a probability of 1/7, and week day axis labels.

bar(c)
axis([0 8 680 690])
avg = 4800/7;
line([0 8], [avg avg],'linewidth',4,'color','black')
set(gca,'xticklabel',{'Su','M','Tu','W','Th','F','Sa'})

The probability for Friday is

p = c(6)/4800;
fprintf('p = %8.6f\n',p)
fprintf('1/7 = %8.6f\n',1/7)

p = 0.143333
1/7 = 0.142857

So, the 13th of a month is more likely to occur on Friday that any other day of the week. Only slightly more likely, I admit, but still ...

Published with MATLAB® 7.14

|


text:
Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

22 Jun 2012Vadym KliuchnikovDmitri MaslovMichele Mosca

In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used... (read more)

PDF Abstract

No code implementations yet. Submit your code now


text:
63 206
Assignments Done
99,3%
Successfully Done
In July 2018

Answer to Question #50824 in Microeconomics for asif

Question #50824
Use the production function: Q=10K^0.5L^0.6, suppose that the wage rate is $28, the price of capital also is$28, and the firm currently is producing 30.3 units of output per period using four units of capital and two units of labor. Is this an efficient resource combination? Explain. What would be a more efficient (not necessarily the best) combination? Why? (Hint: Compare the marginal products of capital and labor at the initial input combination.)
Q=10K^0.5L^0.6, w = $28, k =$28, Q = 30.3 units, K = 4 units, L = 2 units.
MPL = Q'(L) = 6K^0.5/L^0.4
MPk = Q'(K) = 5L^0.6/K^0.5
Marginal rate of technical substitution MRTS = MPL/MPk =
(6K^0.5/L^0.4)/( 5L^0.6/K^0.5) = 1.2*4/2 = 2.4, so we need 2.4 units of K
for every unit of L.
So, K = 4 units and L = 2 units is not an efficient resource
combination. A more efficient combination will be 4.8 units of K and 2
units of L.

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!


text:
# Rates & Ratios

A ratio is a comparison of two numbers. A ratio can be written using a colon, $3:5$ , or as a fraction $\frac{3}{5}$ .

A rate , by contrast, is a comparison of two quantities which can have different units. For example $5$ miles per $3$ hours is a rate, as is $34$ dollars per square foot.

Example 1:

A punch recipe calls for $6$ ounces of lime juice, $21$ ounces of apricot juice, and $21$ ounces of pineapple juice. What is the ratio of lime juice to apricot juice?

Writing the ratio using a colon, we get $6:21$ .

Note that this can be reduced, like a fraction, by dividing both numbers by a common factor -- in this case, $3$ . In simplest form, the ratio is $2:7$ .

Example 2:

In the recipe above, what is the ratio of apricot juice to the total amount of punch?

To find the total amount of punch, add $6+21+21=48$ .

The ratio of apricot juice to the total amount of punch is $21:48$ . But this ratio is probably more clearly written as a fraction, since the apricot juice makes up a fraction of the whole.

$\frac{21}{48}$

To reduce the fraction, divide both the numerator and the denominator by $3$ .

$\frac{7}{16}$

Note that this can be reduced, like a fraction, by dividing both numbers by a common factor -- in this case, $3$ . In simplest form, the ratio is $2:7$ .

Example 3:

An adult scolopendromorph centipede has $46$ legs and $8$ eyes. In a group of $100$ centipedes of the same species, what is the ratio of legs to eyes?

Note that it doesn't matter if there are $100$ or $10,000$ centipedes; the ratio of legs to eyes will remain the same.

Writing the ratio using a colon, we get $46:8$ .

Divide both numbers by $2$ . In simplest form, the ratio of legs to eyes is $23:4$ .

Example 4:

A bat beats its wings $170$ times in $10$ seconds. Write the rate as a fraction in lowest terms.

Write the rate as a fraction.

$\frac{170\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{wingbeats}}{10\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{seconds}}$

Divide both the numerator and the denominator by ten.

$=\frac{17\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{wingbeats}}{1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{second}}$

So, the rate is $17$ beats per second.

Example 5:

A mountain climber is $3200$ meters from the peak. He climbs $50$ meters per hour for $8$ hours per day. How many days will it be before he reaches the peak?

The first job is to figure out the rate per day.

$\frac{50\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{meters}}{1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{hour}}\cdot \frac{8\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{hours}}{1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{day}}=50\left(8\right)\frac{\text{meters}}{\text{day}}$

$=400\frac{\text{meters}}{\text{day}}$

He is climbing at a rate of $400$ meters per day.

Now divide $3200$ by the daily rate to find the number of days it will take him to reach the top.

$\frac{3200\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{meters}}{400\frac{\text{meters}}{\text{day}}}=8\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{days}$


text:
## March 16, 2012

### Speed Reading: Taking care, moving backwards, slowing down…

Tutor was Han-Na Cha.

Let’s comment on the second one first, because that’s shorter. If a summary, or key point list, is offered at the end, it’s convenient to do that -> section headings -> start, linearly forward to get some indication of where it’s going and which parts to skip over. If not, the section headings themselves offer a decent summary (often, yet not always).

Onto the first: reading symbols. We begin, naturally, with an example.
$(\forall x,y)(\forall \epsilon > 0)(\exists \delta)(|x-y|< \delta \Rightarrow |f(x)-f(y)|<\epsilon)$
This one is the definition of continuity of a function $f$ everywhere. Once again, the brackets here provide an obvious chunk. Draw attention, here, to the first triplet:
$(\forall x,y)(\forall \epsilon > 0)(\exists \delta)$
This is /also/ a chunk: that is, it’s a combination you see a lot, and it’s also the initiation step for this sentence: we have initiation, followed by statement. It’s also importantly different from
$(\forall \epsilon > 0)(\exists \delta)(\forall x,y)$
which is used for uniform continuity, despite sharing all three chunked phrases, with two paired.

Unsurprisingly, it turns out the way to get better at reading is to read more, and look out for the patterns that emerge.

### One comment

1. #### Han-na Cha

Hi Chris,

Thanks for clarifying the action points. Good update – I’ve been on holiday for 2 weeks so going to read your updates from this one.

10 Apr 2012, 16:28

You are not allowed to comment on this entry as it has restricted commenting permissions.

## March 2012

Mo Tu We Th Fr Sa Su
Feb |  Today  | Apr
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31

## Galleries

• Nice proof! Does this mean you're going to specialize in analysis and differential equations next ye… by Nick on this entry
• Hi Chris, It was most interesting to read your various reflections – thank you for sharing them. I'm… by Ceri Marriott on this entry
• Feel free. Chris by Christopher Midgley on this entry
• Hi Chris This is an honest final entry for the WSPA. Im glad that you have found the WSPA journey wo… by Samena Rashid on this entry
• Knowing the maximum price you would be comfortable with paying for X is extremely useful for compani… by Nick on this entry


text:
## ZN’s website

If you find yourself with absolutely nothing to do, check out my Churchill college website. There is currently almost nothing on it, but the notable thing that is there is a link to my $\LaTeX$ed Part III Commutative Algebra notes, customis(z)ed for the Kindle! In accomplishing this Kindle-friendly-is(z)ing, I benefited greatly from the TeX.SE answers here and here. I’m very pleased with the results:

I hope someday there will be a tool to convert $\TeX$ source files to Kindle-friendly source files, as described in the first TeX.SE question. I also hope people are working on making $\LaTeX$ create reflowable PDFs.


text:
## Problem #024 - hats in a line

Some people are standing quiet in a line, each person with a hat that has one of two colours. How many people can guess their colour correctly?

# Problem statement

Some people, let's say $$n$$ people, are standing in a line. (Of course they are more than 2m away from each other, social distancing has to be taken seriously by all of us.)

Each person has a hat, like the picture above shows. Each hat is either light or dark, but no one knows the colour of their own hat and people can only look forward and cannot move at all. (Except perhaps to blink and to breath.)

Assuming they got a chance to meet before they got placed in a line and received their hats, what strategy do they have to agree on so that the most people can guess their own hat colour correctly? We can pretend that people who fail to guess their hat colour are sent to prison, and of course we want to keep as many people out of prison as possible. The only thing they know is that the hats will be distributed randomly, they have no idea how many hats of each colour will be distributed.

So your task is to devise the best possible strategy and to find out how many people that strategy saves, on average.

It is important to note that:

• people cannot communicate with each other once they are in a line;
• they can try to guess the colours of their hats in any order you see fit;
• each person gets a single attempt;
• everyone hears everyone's guess, but only the people behind the person making a guess know if that person got it right. Everyone else has no idea if the guess was correct or not.

If you need any clarification whatsoever, feel free to ask in the comment section below.

This problem was posed to me by my friend LeafarCoder.

# Solution

Let us say there's $$n$$ people standing in the line. We will show that the best strategy always saves $$n - 1$$ people and that the $$n^\text{th}$$ person is saved with a $$50\%$$ probability.

In order to do this, we have to do two things:

1. Show there is no strategy with a better success rate.
2. Show there is a strategy with this success rate that works.

In approaching problems of this type, where one has to “find the best strategy possible”, my approach is often one of a wishful thinker. If someone poses a problem like this, usually it's because there is an amazing strategy with a very good success rate. When that is the case, I always try to see if there can be a perfect strategy. More often than not, there is a perfect strategy or one that comes quite close to it.

For this particular problem, it is easy to see there cannot be a truly perfect strategy: the first person that guess their own hat will have no information whatsoever. Other than the colours of the hats of the other people, of course, but those are completely independent from the colour of their own hat. This means the first person will never be able to do better than randomly guessing, which has a $$50\%$$ success rate.

It is after the first person guesses their hat that things get interesting, because the person that guesses first can use their guess to convey some information to the other $$n - 1$$ people and, if we do this right, that information can help the next people to guess their hat correctly.

I'll show you how to do this. To make explaining the strategy simpler, let us identify dark hats with the number $$1$$ and light hats with the number $$0$$.

The first person that will say something will be the one at the end of the line, as that is the person that has more information available, because they can see everyone else in the line. Let me illustrate the explanation with an example, assuming $$n = 6$$ and that the hats are $$1~0~0~1~1~0$$, assuming the first person (the person that sees everyone) has the black hat represented by the first $$1$$ from before.

The first person thus knows that the hats are distributed like this $$?~0~0~1~1~0$$, with the only unknown being their own hat.

The first person will then sum the value of every hat in front of them, which would be $$2$$ in this case, and check the parity of that number (i.e. answer the question “is the number even or odd?”). $$2$$ is even, of course.

The first person is then tasked with letting the others know what is the parity of what their hats add up to, so that like a domino all of them guess their hats correctly.

In our example, $$2$$ is even and so the first person guesses that their hat is light-coloured, because that is the colour associated with $$0$$. (Unfortunately, this is one of the cases where the first person doesn't make it but their sacrifice saved everyone else!) After that, the second person in line knows that their hat, plus the others in front of them, have a specific parity.

The second person can see $$n - 2$$ hats and knows their parity. On top of that, the second person knows what is the parity of the $$n - 1$$ hats, because the first person told them that. This means that the second person can know the parity of its own hat. In our example, the second person sees hats that sum to $$2$$, which is even, and they also know that $$2$$, plus their hat, should give an even number. The second person concludes that their hat is represented by $$0$$ and is thus light-coloured.

Then the process is repeated. Let us prove with induction that this works well. We will prove that if persons $$2, 3, \cdots, k$$ get it right, then so does the $$(k + 1)^\text{th}$$ person, where the base case is for $$k = 2$$. The base case was already proven, so we are left with the induction step.

Let $$h_i$$ represent the number associated with the hat owned by person $$i$$. In our example we have $$h_1 = h_4 = h_5 = 1$$ and $$h_2 = h_3 = h_6 = 0$$. Our induction hypothesis tells us that we know the values of $$h_2, \cdots, h_k$$ (because those people guessed their hats correctly) and that we also know the parity of $$t = h_2 + h_3 + \cdots + h_n$$, because the parity of $$t$$ is the hint that the first person gives us. Finally the $$(k + 1)^\text{th}$$ person can see, with their own eyes, the values of $$h_{k+2}, \cdots, h_n$$. In essence, $$t$$ is the sum of $$n - 1$$ variables and person $$k + 1$$ knows $$n - 2$$ of those values, meaning they can determine $$h_{k+1}$$:

$t - \left(h_2 + \cdots + h_k \right) - \left(h_{k+2} + \cdots h_n \right) = h_{k+1} \text{ mod } 2$

Of course we can only do this $$\text{mod } 2$$ because we can only work with parities, but that is enough.

This is the proof that the strategy works. I will now complete the example we had been going over.

The third person knows the hats are like this: $$?~0~?~1~1~0$$ and knows that $$0~?~1~1~0$$ should add up to something even.

The third person can then guess their hat is light-coloured, because $$0~+~? + 1 + 1 + 0$$ only adds up to something even if their hat (the $$?$$) is $$0$$.

Next is the fourth person, that knows the hats are like this: $$?~0~0~?~1~0$$ and knows that $$0~0~?~1~0$$ should add up to something even.

The fourth person can then guess their hat is dark-coloured, because $$0 + 0~+~? + 1 + 0$$ only adds up to something even if their hat is $$1$$.

Next is the fifth person, that knows the hats are like this: $$?~0~0~1~?~0$$ and knows that $$0~0~1~?~0$$ should add up to something even.

The fifth person can then guess their hat is dark-coloured, because $$0 + 0 + 1~+~? + 0$$ only adds up to something even if their hat is $$1$$.

Next is the sixth, and final, person, that knows the hats are like this: $$?~0~0~1~1~?$$ and knows that $$0~0~1~1~?$$ should add up to something even.

The last person can then guess their hat is light-coloured, because $$0 + 0 + 1 + 1~+~?$$ only adds up to something even if their hat is $$0$$.

And that is it! I hope my explanation was clear!


text:
# Show that $c_0$ is a Banach space with the norm $\rVert \cdot \lVert_\infty$

Let $c_0 = \{ x = \{x_n\}_{n \in \mathbb N} \in l^\infty : lim_{n \rightarrow \infty} x_n = 0\}$. Show that $c_0$ is a Banach space with the norm $\rVert \cdot \lVert_\infty$

I am capable of showing the space where the limit of $x_n$ exists is normed linear space but am having trouble with showing that the limit of Cauchy sequences must converge to 0.

Let $(x^{(n)})_{n \in \mathbb N}$ be a Cauchy sequence in $c_0$ such that $x^{n} = (x^n_1, x^n_2,...)$. Fix $k \in \mathbb N$ consider the sequence $(x^n_k)_{n \in \mathbb N}$ in $\mathbb F$. For any $n,m \in \mathbb N$

$\lvert x^n_k - x^m_k \rvert \le sup_{k \in \mathbb N} \lvert x^n_k - x^m_k \rvert = \lVert x^n - x^m \rVert_\infty \lt \epsilon$ (1)

Thus $x^n_k$ is Cauchy in $\mathbb F$ and so has limit $y_k$ such that $y = (y_1,y_2,...)$ and y is the limit of $x^n$

To show that such a y exists we look at the value of $\lvert y_n - y_m \rvert \le \lvert y_n - x^N_n \rvert + \lvert x^N_n - x^N_m \rvert + \lvert x^N_m - y_m \rvert \lt \epsilon$ for all $n,m \ge N$ (2)

The middle expression on RHS of (2) is $\lt \epsilon/3$ by (1)

The other two are also $\lt \epsilon/3$ follow from $x^N_k$ being Cauchy and converging to $y_k$

This shows that $lim_{n \rightarrow \infty} y_n$ exists but we still have not shown that $y \in c_0$.

I know that to show y tends to 0 i should show that $\lvert y_k \rvert \lt \epsilon$ for $k \ge N$

This is where I am stuck. Perhaps $\lvert y_k \rvert = \lvert lim_{n \rightarrow \infty} x^n_k \rvert$ and then we can take the limit function outside the absolute value sign by continuity? Then we might say due to it being a Cauchy sequence $x^n_k \lt \epsilon$. I know this last bit isn't at all convincing so I could do with some help.

• First show $(x^{(n)})$ converges to the pointwise limit $y$ in $\ell_\infty$. Given $\epsilon>0$, choose $N$ so that $\Vert x^{(N)}-y\Vert<\epsilon/2$. Then choose $M$ so that $|x^{(N)}(i)|<\epsilon/2$ for $i>M$. Then $|y(i)|<\epsilon$ for $i>M$ by the triangle inequality. – David Mitra May 10 '15 at 16:48

## 2 Answers

Suppose $x^k \in c_0$ and $x^k \to x$. Let $\epsilon>0$ and pick $N$ such that $\|x^k-x\|_\infty < {1 \over 2 } \epsilon$ for $k \ge N$. Since $x^N \in c_0$, there is some $N'$ such that $|x_i^N| < {1 \over 2 } \epsilon$ for $i \ge N'$. Then $|x_i| \le |x_i^N| +|x_i-x_i^N| \le |x_i^N| +\|x-x^N\|_\infty <\epsilon$. Hence $x_i \to 0$ and so $x \in c_0$.

Hence $c_0$ is a closed subspace of $l_\infty$.

It follows that $c_0$ is Banach since $l_\infty$ is Banach (any Cauchy sequence in $c_0$ is Cauchy in $l_\infty$ hence converges to some point an closedness shows that this point lies in $c_0$).

We note that $$|y_k| \leq |y_k - x^n_k| + |x^n_k| = \lim_{m→∞}|x^m_k - x^n_k| + |x^n_k| \leq\lim_{m→∞} ‖x^m - x^n‖ + |x^n_k|$$ which holds for arbitrary $n$. (the superscript is which sequence, the subscript is the index of the sequence) As $x^n∈ c_0$, choose $K_n$ large such that $|x^n_k |<ε$ for $k>K_n$.

Pick $N(ε)$ large such that $\|x^m - x^n||<ε$ for $n,m>N$. Taking limits($\star$) gives $$\lim_{m→∞}‖x^m - x^n‖ \leq ε \quad ∀ n \geq N$$

So putting the two bounds together: With $ε>0$ given, there is $K = K_{N(ε)}$ such that $$|y_k| \leq \lim_{m→∞} ‖x^m - x^{N(ε)}‖ + |x^{N(ε)}_k| \leq 2ε$$ for all $k > K$.

The step marked $(\star)$ is easy to see if you notationally suppress the $n$: $$a_m < ε ∀ m > N \implies \lim a_m \leq ε$$ as (you have shown) this limit will exist.