# Market Potential for CO2 Removal and Sequestration from Renewable Natural
Gas Production in California

Jun Wong
UC Berkeley, Environmental Science, Policy, and Management & NYU Stern
Jonathan Santoso
UC Berkeley, Chemical and Biomolecular Engineering  Marjorie Went
UC Berkeley, Chemical and Biomolecular Engineering  Daniel Sanchez
UC Berkeley, Environmental Science, Policy, and Management

Correspoding author<EMAIL_ADDRESS>
(May 2021)

###### Abstract

Bioenergy with Carbon Capture and Sequestration (BECCS) is critical for
stringent climate change mitigation, but is commercially and technologically
immature and resource-intensive. In California, state and federal fuel and
climate policies can drive first-markets for BECCS. We develop a spatially
explicit optimization model to assess niche markets for renewable natural gas
(RNG) production with carbon capture and sequestration (CCS) from waste
biomass in California. Existing biomass residues produce biogas and RNG and
enable low-cost CCS through the upgrading process and CO2 truck transport.
Under current state and federal policy incentives, we could capture and
sequester 2.9 million MT CO2/year (0.7% of California’s 2018 CO2 emissions)
and produce 93 PJ RNG/year (4% of California’s 2018 natural gas demand) with a
profit maximizing objective. Existing federal and state policies produce
profits of $11/GJ. Distributed RNG production with CCS potentially catalyzes
markets and technologies for CO2 capture, transport, and storage in
California.

Keywords: Biogas, Carbon capture, Renewable natural gas, BECCS, Niche markets

## Introduction

Deep decarbonization of the energy system critically relies on Bioenergy with
Carbon Capture and Sequestration (BECCS) to produce low-carbon and carbon-
negative products such as heat, electricity, and fuels (1). Current BECCS
deployment has been lagging the scales envisaged in century-scale climate
change mitigation scenarios. Instead it is limited to a handful of
demonstration projects in corn ethanol and waste-to-energy production (2, 3,
4). Based on this disparity, numerous scholars have argued for a “bottom up”
approach to BECCS commercialization based on niche markets, scale-up,
regionally appropriate feedstocks, and local policies (5, 6, 7). In these
contexts, small-scale (megatonne scale) commercially viable opportunities for
BECCS are necessary to promote more widespread adoption of carbon removal.
Technology and policy analyses that identify opportunities to leverage
existing infrastructure, deploy existing technologies, and capitalize on
current policies can enhance mitigation efforts by developing experience in
carbon capture, transport, sequestration, and removal (2). Moreover,
establishing first-markets for BECCS-use can further incentivize and
accelerate innovation in this field. We explore such an opportunity in
California (CA), producing renewable natural gas with carbon capture and
sequestration (RNG-CCS).

California is well-positioned for BECCS implementation. The state’s economy
yields large volumes of waste biomass from forestry, urban and agricultural
activities. In total, California produced 54 million bone dry tons (BDT) of
biomass residues in 2018 (8). This is projected to grow to 71 million bdt per
year by 2050. At the same time, its geography is well-suited for CO2 storage
(9). Over 24,000 km2 of non-urban area in the Central Valley, Bay Area, North
Coast, and greater Los Angeles area (10% of California’s total land area) is
suitable for CO2 sequestration (Figure 1). In total, the state has over 200
GtCO2 of total sequestration capacity. We estimate that in-state capacity-
weighted sequestration costs are around $1.35/tCO2 (2)111This estimate
includes injection and monitoring costs. Please refer to Sanchez et al. (2)
and the supplmentary information..

Current state and federal fuel and climate policies can drive first-markets
for BECCS in California. In particular, the California Low Carbon Fuel
Standard (LCFS), federal 45Q carbon sequestration tax credit, and federal
Renewable Fuel Standard (RFS) can all be used to incentivize BECCS.
Established in 2011, California’s LCFS provides financial incentives for low-
carbon and carbon-negative transportation fuels through tradeable CO2
abatement credits (10). In 2019, California’s Air Resources Board amended the
LCFS to allow for CCS projects to generate additional LCFS credits (11).
Abatement credits are performance-based, proportionate to the carbon intensity
reduction relative to a benchmark fossil fuel (E100). Historical credit prices
ranged from $160-192 tCO2 abated between 2018-2020. In 2018, the federal
government enhanced its existing tax credit for geologic CO2 sequestration,
providing 45Q tax credits as high as $50/tCO2 sequestered for dedicated
storage for facilities capturing over 100,000 tCO2 per year. In addition, the
federal RFS subsidizes the production of renewable fuels through the
distribution of Renewable Identification Number (RIN) credits. Various
biofuels are eligible to receive different classes of RIN credits on a volume-
basis (one credit is a Gallon Gasoline Equivalent (GGE)): lignocellulosic
biofuels receive D3 credits, which often receive higher prices, while
“advanced” (non-corn starch) biofuels receive D5 credits. D3 credits have
traded at 0.59-2.74 $/GGE in 2018-2020, while D5 credits have traded at
0.38-0.85 $/GGE.

In recent years, California’s waste management policies have been in favor of
biomass utilization. SB 1383, signed into law in 2016, is a broad methane
reduction strategy in California that targets a 40% decrease in methane
emissions by 2030 and 75% decrease in organic waste sent to landfills by 2025.
The bill specifically targets dairy emissions: it requires a 40% decrease of
dairy production-related methane emissions by 2030. Beyond dairy, the
legislation targets a 50% reduction in the level of the statewide disposal of
organic waste from the 2014 level by 2020 and a 75% reduction by 2025 (12).
SB1383 necessitates innovative methods to process waste biomass. Anaerobic
digestion, electricity generation, biochar production for land application,
and composting are all methods that can utilize the available biomass residues
and potentially meet the SB1383 goals. Of these applications, RNG-CCS through
anaerobic digestion is a particularly attractive candidate to meet both the
organic waste diversion and methane emissions goals while simultaneously
producing carbon-negative fuels.

Given the policy and resource context, California has seen large growth in
biogas and renewable natural gas production from biomass via anaerobic
digestion and landfill gas collection. Anaerobic digestion, a sequence of
processes by which microorganisms break down biodegradable material in the
absence of oxygen, has been used as a technology for waste management and
renewable fuel production. We estimate that 46 anaerobic digester (AD) sites
process food waste, municipal solid waste, and dairy waste in California as of
2019 (13, 14, 15). Furthermore, 154 existing wastewater treatment plants
process wastewater and 52 landfills are equipped with existing landfill gas
(LFG) collection systems (16). We estimate roughly 3 million mmbtu of biogas
is produced per year from anaerobic digesters and 10 million mmbtu of landfill
gas is diverted to various cogeneration projects in California. All but five
AD projects in California are generating electricty and/or heat. More
recently, producers are starting to upgrade biogas into renewable natural gas
(RNG) for injection into California’s natural gas distribution system. RNG has
entered markets as a low-carbon transportation fuel, in part due to subsidies
from the RFS and LCFS. For instance, the Calgren facility in Pixley and the
CR&R facility in Perris generate RNG from manure and food waste, respectively.

Despite the recent development of RNG facilities in California, the several
existing facilities in California do not incorporate RNG production with CCS
despite the fertile policy environment and geologic endowment in California.
Producing RNG from biogas presents an opportunity for low-cost CO2 capture.
Biogas contains a mixture of CH4 and CO2, along with other trace contaminants.
The upgrading process separates CH4 from other components of biogas, producing
not only a pure stream of CH4, but also a relatively pure stream of CO2. In
particular, Pressure Swing Adsorption (PSA) separates the CH4 and CO2 in
biogas and produces a stream of 75-98% pure CO2 (17, 18). To our knowledge,
RNG-CCS is relatively under-studied in the literature despite the attractive
low-cost opportunity for CO2 capture. Most recently, Esposito et al. (19)
reports that the production of food-grade CO2 from biogas upgrading (99.9%)
can be profitable in Italy.

Here, we develop a spatially explicit optimization model to assess the near
term opportunities for RNG production from waste biomass with CCS in
California under existing policy incentives (Figure 2). We incorporate high-
resolution data on existing biomass residues, anaerobic digesters, wastewater
treatment plants, landfills, truck networks, and geologic sequestration sites
in California. Profitable RNG production with CCS has the potential to
catalyze markets and technologies for CCS and BECCS in California.

## Methods

### Data Development

We compile a database of available biomass residues (feedstocks) in California
from various sources. Data on municipal solid waste (MSW), crop residues, and
manure are from Breunig et al. (8). We supplement these with data on
wastewater treatment plants and daily average flows from the California
Association of Sanitation Agencies (CASA). Lastly, we collect landfill
locations and volumes of landfill gas from EPA Landfill Methane Outrech
Program (LMOP). We estimate the current deployment of anaerobic digesters in
California using the EPA AgStar database on dairy digesters (13), Argonne
National Lab RNG database (14), EPA LMOP database (16), and CalRecycle (15).
We consider locations for new digesters in cities with population greater than
10,000 and less than 5 km away from an existing natural gas pipelines. Saline
aquifer storage capacities and locations are derived from v1502 of the
National Carbon Sequestration Database (SI Text) (20). We use the open source
routing machine (21) to calculate the shortest road distance and time between
point sources and facilities, and facilities to sequestration sites. To avoid
the computational limitations, we limit feedstock and CO2 transport to within
50 miles.

We derive the cost of anaerobic digesters, biogas upgrading, and RNG injection
from Parker et al. (22) (SI text). We use the biomass transport cost provided
in Tittmann et al. (23). We use the cost of CO2 capture and transport provided
in Psarras et al. (24), and CO2 compression and pumping cost from McCollum and
Ogden (25). To calculate the costs of CO2 sequestration in saline aquifers, we
supplement the methods of Sanchez et al. (2) with the C2SAFE model for
California-specific policy related costs, such as seismic monitoring (26). We
convert all costs to 2019 US dollars using the Information Handling Services
(IHS) Upstream Capital Cost Index. We assume a 15-year project timeline and
10% internal rate of return. We assume that all the RNG produced is used to
supply compressed natural gas (CNG) in California as transportation fuel.
Thus, the RNG is eligible to receive Renewable Identification Numbers (RINs)
under the Renewable Fuels Standard. The RNG produced is also eligible to
receive the Low Carbon Fuel Standard (LCFS) credits and 45Q carbon
sequestration credits (given the 100,000 tCO2 captured per year threshold is
met), and the market price for CNG.

We mainly use biogas yields from Li et al. (27), but we also compile a range
of biogas yields for various feedstocks from a broader literature
investigation (SI Text). We assume that the resulting biogas is comprised of
60% CH4 and 40% CO2. To determine the amount of LCFS credits, we take the
carbon intensity of the RNG produced from the California Air Resources Board
(11). Additional sequestered CO2 also earn LCFS credits. We assume that the
system uses California grid electricity for capture and compression, with
carbon intensity equal to the average California mix in 2018 (28). We also
assume for CO2 transport an emissions factor of 161.8 gCO2/ton-mile (29). Note
that the feedstock transport emissions factor is already accounted for in the
GHG intensity provided by the Air Resources Board.

We build a spatially explicit optimization model informed by data on biomass
residues, existing anaerobic digesters, wastewater treatment plants,
landfills, road networks, and geologic sequestration sites in California
(Figure 2). In this paper, we offer two novel methodological contributions to
the literature on spatial optimization of biomass and CCS. We model for
codigestion and consider trucking networks for CO2 transportation. We contend
that the codigestion of feedstocks offers greater economies of scale and
flexibility to the system. Additionally, the relatively small amounts of CO2
produced in this context do not justify pipeline construction for the sole
purpose of transporting several million tons of CO2. In particular,
California’s siting and permitting processes are not conducive for near-term
development of CO2 pipelines.

### Problem Statement and Scenarios

We minimize the net total cost of the production of RNG and sequestration of
CO2 using mixed integer programming to identify cost-effective sequestration
opportunities (Figure 2). We define two binary decision variables that
indicate the activation of facilities and sequestration sites, respectively.
The six continuous decision variables are: the quantity of feedstock delivered
to facility, amount of biogas produced, amount of CO2 captured from the biogas
upgrading process, amount of CH4 produced from the biogas upgrading process,
amount of CO2 transported to each sequestration site and the amount of CO2
sequestered at each sequestration site. Our model is implemented in AMPL and
solved using a branch-and-bound method. The model’s complexity yields
optimality gaps of 10-20%–implying that solutions are feasible but not
necessarily optimal.

Within each scenario, we assume a range of market price of RNG, and credit
prices of LCFS, RIN, and 45Q. We detail the system boundaries in the SI. In
practice, price volatility, policy uncertainty, lifecycle emissions
accounting, and tax equity availability will all affect the cost-effectiveness
of CCS projects that is dependent on tax credits and tradeable permits. We do
not explicitly model for other potential revenue streams, such as CO2
utilization options (EOR or beverage carbonation) or alternative feedstock
uses.

### Data Access

Existing pipeline rights of way are available here. National Carbon
Sequestration database on saline aquifers are available here. The EPA Landfill
and Outreach Program database is available here. Existing agricultural
digester database in the U.S. can be found at the EPA AgStar database,
available here here. Our model and a reproduction kit is available on GitHub.

## Results and Discussion

To characterize the optimal deployment of RNG production with CCS in
California (RNG-CCS) under current policy conditions, we present key model
outputs—RNG produced, CO2 sequestered, costs, revenues, and profits—under a
range of policy scenarios (Figure 3). Policy scenarios are constructed around
recent prices available under Section 45Q, California’s LCFS, and the federal
RFS (Table 1). Further information about our methods and assumptions is
available in the Methods and SI Text.

California’s economy yields large volumes of waste biomass–we use as basis the
estimated 54 billion bdt of biomass residues available from crop residues,
municipal waste, and manure per year in 2020 (8). Additionally, exisiting
landfill gas facilities and wastewater treatment facilities collect 5.3
million m3 landfill gas and 2.82 million gallons of wastewater per day,
respectively. Taken together, these sources can produce up to 146 PJ RNG per
year, or 6.5% of the natural gas demand in California in 2018, and 5 million
tons CO2 per year for potential sequestration (30).

In the baseline scenario, 79 facilities profitably produce 93 PJ of RNG per
year (a near ten-fold increase over present levels) and sequester 2.9 million
tons of CO2 per year in 18 sequestration sites. The volume of CO2 sequestered
at each site ranges up to 515,000 tons CO2 per year. Economies of scale apply
to CO2 sequestration: the median sequestration site is shared among 3 RNG
facilities, each transporting CO2 an average of 26 miles. The amount of RNG
produced makes up roughly 4% of current natural gas usage in California, or
roughly 3 times the current demand for utilizing natural gas as transportation
fuel.

The baseline utilizes municipal solid wastes (MSW) heavily: facilities
annually process a total of 711,400 wet tons (wt) of food waste, 1.4 million
wt of green waste, and 110,601 wt of grease, with an average transport
distance of 20 miles. The scenario takes advantage of the colocation of
agricultural activity and sequestration sites in the Central Valley—4.8
million wt of available crop residues and 23 million wt of manure are
utilized. On average, crop residues are transported 26 miles and manure
feedstocks are transported 15 miles from source to processing facility.

Our model generates networks of regional carbon negative biomethane production
networks that exploit the diversity of feedstocks in the state in the optimal
baseline scenario. Facilities tend to cluster near urban regions with readily
available MSW. Broadly, we observe six distinct regions of agglomeration
within California: in urban regions such as the greater Los Angeles area, Bay
Area, Sacramento Valley; and agricultural regions around Bakersfield and
Imperial County (Figure 3). CO2 sequestration in non-urban areas is
economically feasible in all regions due to the widespread regional
availability of sequestration sites.

In the optimal scenario, we see significant heterogeneity in feedstock
utilization in different parts of California and notable differences in
landfill gas usage in urban areas. Landfill gas plays a significantly larger
role in the Bay area and greater L.A. area compared to the Central Valley. In
the Bay Area, landfill gas produces 87% of the total RNG, compared to 6.5% in
Fresno. Overall, landfill gas make up roughly 39% of the total RNG production.
Manure, an important feedstock in certain regions, produces 70% of the total
RNG in Fresno and 99% in Imperial County, taking advantage of the livestocks
in these regions. The ability of the RNG-CCS system to process all varieties
of biomass residues makes for an attractive option to produce carbon negative
fuels across California.

The baseline results above suggest that the current policy climate is
sufficient to incentivize a robust build out of RNG-CCS systems in California.
However, should existing policies be sharply curtailed, the RNG-CCS system
could potentially lose its economic viability. To further investigate, we
consider four policy scenarios: low and high policy support scenarios, a no
RFS scenario, and no 45Q minimum threshold scenario (Table 1). In the ”High
Policy” scenario, we extend the policies to their allowed maximum.
Specifically, we assume that the LCFS price is increased to $200 per credit,
RFS price to $1.50 per credit, and 45Q remains at $50 per ton CO2. In the ”Low
Policy” scenario, we lower policies to their minimum: the LCFS price is
decreased to $20 per credit, the RFS credits become zero, while 45Q remains at
$50 per ton CO2. The ”No RFS” scenario entails removing RFS credit incentives
while all else is as in the baseline scenario. We remove the minimum 100,000
CO2 captured per year threshold to receive the 45Q tax credit in the ”No 45Q
Minimum Threshold” scenario while keeping all else equal.

In the favorable policy environment of the ”High Policy” scenario, 4 million
tons of CO2 is sequestered in 36 sites and 130 PJ of RNG is produced per year
from 121 facilities. With significantly lower policy support in the ”Low
Policy” scenario, we still find that 1 million tons of CO2 is sequestered in 8
sites and 32 PJ of RNG is produced per year from 37 facilities. Without RFS at
baseline, we find that the baseline levels of LCFS and 45Q credits are
sufficient to sustain a similar level of RNG-CCS build out in California. We
still sequester 2.3 million tons of CO2 in 14 sequestration sites and produce
73 PJ of RNG from 61 facilities (Figure 4(b)). This represents a 22% decrease
in RNG production from the baseline scenario. Removing the minimum threshold
100,000 tons of captured CO2 for 45Q eligibility does not increase the RNG-CCS
build out in an optimal scenario. Instead, it produced 90 PJ of CH4 in 95
facilities and sequesters 2.8 million tons of CO2 in 27 sequestration sites.

Profits range from $3 and $32/GJ under a low and high policy support
environment, respectively (Figure 5). Without RFS, we find that profits only
decrease slightly compared to the baseline from $11/GJ to $7.4/GJ. Profits
remain roughly similar when we remove the minimum 45Q threshold, earning an
average of $11.50/GJ. LCFS credits remain a significant source of revenue
across all scenarios. Especially without RFS at baseline, LCFS make up an
overwhelming majority (81%) of the revenues earned. Surprisingly, CCS-related
costs are small relative to biomass processing related costs across all
scenarios, making up roughly 10% of the total baseline cost. Biomass
processing related costs dominate: levelized digester costs account for nearly
45% ($6.50/GJ) of the total baseline cost, and feedstock transport costs
account for 42% ($5.93/GJ) of the total baseline cost. Across varying levels
of policy support, we find that the RNG-CCS system is still able to profitably
produce carbon-negative transportation fuel.

Carbon removal through renewable natural gas production with CCS in California
is cost-effective and profitable across the range of scenarios we explore.
This niche market for BECCS holds numerous implications for California’s
climate mitigation efforts, waste management, and energy policy. We discuss
the impacts of existing policies on the build-out of RNG-CCS system in
California (Figure 6(c)).

We find that federal and state support for carbon sequestration is a large
driver of near-term BECCS deployment. To examine the marginal impact of
various policies, we perform sensitivity analysis parametrically. In the
baseline case, existing policies are capable of incentivizing a robust network
of RNG-CCS systems in California while generating $11/GJ of profits. We find
that CO2 sequestration and RNG production are most sensitive to LCFS credit
prices relative to other policy drivers. All else equal, when LCFS credits are
reduced from $100/tCO2 to $0/tCO2, we sequester 1.1 million tons of CO2,
compared to 2.9 million tons of CO2 at the baseline. We only produce 37 PJ of
RNG compared to 93 PJ at the baseline. When LCFS credits are $200/tCO2, we
sequester over 3.8 million tons of CO2 and produce 123 PJ of RNG. RFS also
appears to be an efficient policy driver to incentivize carbon negative
systems relative to the LCFS. CO2 sequestered varies from 2.6 to 4 MtCO2/yr
and RNG production ranges 89 and 131 PJ per year while incentivizing profits
upwards of $19/GJ when we vary the RFS credit price. Taken together, the
results suggest that LCFS and RFS are necessary drivers of RNG-CCS systems in
California. While the LCFS is only officially extended through 2030,
California governor Newsom issued an executive order to the Air Resources
Board (ARB) to extend the LCFS beyond 2030 (31).

Moreover, the 45Q tax credit also plays a complimentary role to LCFS and RFS
credits. As it is currently designed, the tax credit has a minimum CO2
captured threshold of 100,000 tons. In popular press, many argue that the
minimum threshold should be removed for less project finance risks (32). We
show that the threshold is irrelevant in the context of RNG-CCS where the
threshold acts as an agglomeration force without dampening RNG production.
However, the threshold might act as a significant obstacle in pilot projects
with relatively newer technologies or do not produce transport fuels (33).

California is well-suited for systems such as the RNG-CCS system presented
here. The feedstock heterogeneity across regions and abundance of potential of
sequestration sites throughout the state create rich opportunities for low-
cost and near-term carbon negative systems. Moreover, fuel production with CCS
could be an important part of the energy supply mix that satisfies low-carbon
fuel mandates in California and the United States. Other low-carbon and
carbon-negative fuel technologies with CCS such as ethanol coupled with CCS,
enhanced oil recovery (EOR), Direct Air Capture with EOR (DAC-EOR), and many
others, could become important under current policy conditions (2, 34).

Yet, we stress that RNG-CCS is not a substitute for electrification in
California—at baseline, it produces only 4% of current natural gas demand. If
we electrify rapidly according to the E3 PATHWAYS high building
electrification scenario, RNG-CCS at baseline would meet 42% of the RNG demand
and 14% of the overall natural gas demand (35). In contrast, if we do not
electrify effectively, the baseline RNG production would meet over 100% of the
RNG demand and only 7% of the overall natural gas demand. Despite this, the
RNG-CCS system could be attractive to supply transportation fuel in
California, and serve as a first market for CCS in California.

RNG-CCS can promote broader CCS deployment in California. We find that sharing
sequestration sites across different CCS projects can further lower the
capital cost of CO2 sequestration while ensuring effective monitoring and
verification. Existing efforts by the Department of Energy’s C2SAFE program
aim to sequester 50 million tons of CO2 over 20 to 30 years (26). Furthermore,
sequestration and abatement credits to drive CCS first markets can develop
experience, project financing, policies, and business models for CCS. Within
California, the Central Valley is prime to emerge as a hub for CCS. Baker et
al. (9) describe the central valley as “ready to go” to address CO2 storage
needs. Further work is necessary to enable sequestration at sites near urban
areas, which here we assume cannot be utilized.

We note several key limitations to our current modeling framework. First, we
assume that the natural gas produced can be injected into the natural gas
pipeline network in California. However, depending on feedstock input and
upgrading technologies, further RNG upgrading to remove any trace amounts of
N2, H2, H2S, O2, and siloxanes may be required. Further, many existing natural
gas pipelines lack adequate capacity (36). We also consider only one type of
waste management in California: anaerobic digestion. Composting is another
viable waste management policy. We do not evaluate the tradeoffs between
composting biomass residues and using biomass residues to produce RNG via
anaerobic digestion. We assume that any potential CH4 emissions from leakage
in the natural gas system is negligible to the climate impacts of reduced GHG
intensity of the RNG and sequestered CO2. However, Grubert (37) finds that RNG
systems could be climate intensive depending on the methane feedstock. The
analysis in this paper is on a yearly basis, but biomass residues, especially
agricultural residues, are seasonal. That is, while average anaerobic digester
capacity predicted by the model is relatively smaller, in reality, digesters
need to be outsized for intermittent large inflows while sitting idle for some
time. Lastly, we consider a global optimization. That is, we optimize for one
collective objective function instead of individual firm objective functions.
Firms make decisions individually, not globally, and a facility-level
optimization might yield different results. The significant economies of scale
involved obviate a need for cost-sharing or redistribution to ensure the
profitability and impact of an RNG-CCS system at a facility scale.

Profitable RNG production with CCS potentially catalyzes markets and
technologies for CO2 capture, transport, and removal in California. In
particular, RNG with CCS can address both the waste management and climate
mitigation needs in California. Producing up to 93 PJ of RNG and sequestering
up to 2.9 million tons of CO2 per year, RNG-CCS can stimulate a robust carbon-
negative system while providing a profitable first market for BECCS. The
deployment of RNG-CCS systems in California can accelerate efforts for BECCCS
internationally and in California. As California considers a broad range of
carbon removal strategies to meet its goal of net neutrality economy-wide in
2045, we suggest that RNG-CCS could play an early and prominent role. More
broadly, RNG-CCS’ success in California can lead to further innovation and
investment in BECCS beyond state borders and substantially impact the federal
climate policy landscape.

## Acknowledgements

We thank Corrine Scown, Curtis Oldenburg, Greg Kester, Hanna Breunig, Maureen
Walsh, Preston Jordan, Tom Richard, and Senorpe Asem-Hiablie for especially
helpful discussions. We acknowledge the support of the Conservation 2.0
program.

Table 1: Policy Scenarios Policies (units) | Baseline | No RFS | No 45Q Threshold | High Policy | Low Policy
---|---|---|---|---|---
LCFS ($/tCO2) | $100 | $100 | $100 | $200 | $20
RFS ($/GGE) | $0.25 | $0 | $0.25 | $1.50 | $0
45Q ($/tCO2) | $50 | $50 | $50 | $50 | $50
45Q Minimum (tCO2/year) | 100,000 | 100,000 | 0 | 100,000 | 100,000

Figure 1: Available biomass residues, existing digesters, and potential CO2
sequestration sites in California

Available biomass residues (green), existing anaerobic digesters and landfills
(blue), and potential CO2 sequestration sites (grey) in California. Colocation
of residues, existing digesters, and potential CO2 sequestration sites across
California reduces biomass and CO2 transportation costs.

Figure 2: System and Model Flow Chart

(a) System Flow Chart

(b) Model Flow Chart

(a) Process flow diagram and (b) Model flow chart for RNG-CCS systems. Panel A
shows major processes in the RNG-CCS system. We consider relevant system
boundaries for lifecycle CO2 emissions assessment consistent with California’s
Low Carbon Fuels Standard. We consider CO2 emissions from CO2 compression,
transportation, and sequestration. Panel B shows major features of our
optimization model. Our optimization maximizes total profits, including binary
decision variables to activate a particular facility or sequestration site,
alongside continuous production decision variables.

Figure 3: Baseline Results

(a) California

(b) Sacramento Area

(d) Fresno Area

(e) Imperial County

(f) Southern California

(g) Bay Area

Baseline RNG-CCS system in (a) California and (b-g) in prominent regional
agglomerations. Across California, RNG-CCS systems produce 119 PJ of RNG from
85 facilities per year, and sequester 4.1 million tCO2 in 19 sequestration
sites per year. In panels B through G, we focus on the emerging regional
agglomerations. Extensive biomass residue and CO2 sequestration collection
networks are formed, enabled by small-volume truck transportation.

Figure 4: Policy Scenarios

(a) Baseline

(b) No RFS

(c) Low Policy

(d) High Policy

(e) No 45Q Threshold

Statewide RNG-CCS system for various policy scenarios: (a) Baseline (b) No
RFS, (c) Low Policy, (d) High Policy, and (e) No 45Q Minimum Threshold. RNG-
CCS systems are robust to varying levels of policy support.

Figure 5: Cost and Revenues

Costs and revenues ($/ GJ) for RNG-CCS system for various policy scenarios.
Costs are separated into two technology categories: CCS-related (red) and
biomass processing-related (orange). Across all scenarios, CCS-related costs
are a small fraction of total costs. Revenues from the LCFS make up a large
share of revenue across all scenarios.

Figure 6: Sensitivity analysis

(a) CH4 production per year

(b) CO2 sequestration per year

(c) Profits per year

Parametric sensitivity analysis of yearly (a) CH4 production (b) CO2
sequestration, and (c) profit. We vary biogas yield, LCFS price, RIN credit
price, RNG price, 45Q credits, and transport cost. Average profits are rarely
fall below the baseline $12/GJ, but can reach as high as $37/GJ when RFS
prices are at their highest.

## References

  * (1) Roger Aines, Giana Amador, David Babson, Drew Bennett, Etosha Cave, Wei Chen, Gregory Dipple, John L. Field, Tim Filley, S. Julio Friedmann, Peter Kelemen, Rory Jacobson, Jason Funk, Johannes Lehmann, Charlotte Levy, Matt Lucas, Karin Matchett, Jessica L. McCarty, Sian Mooney, Nathan R. Neale, Ah-Hyung Alissa Park, Jennifer Pett-Ridge, Joe Powell, Daniel L. Sanchez, Chunshan Song, Ellen Stechel, Nannan Sun, Yuhan Sun, Amy Swan, Jennifer Wilcox, Peter B. Woodbury, and Jane Zelikova.  Building a new carbon economy: An innovation plan.  URL https://static1.squarespace.com/static/5b9362d89d5abb8c51d474f8/t/5b98383aaa4a998909c4b606/1536702527136/ccr02.innovationplan.FNL.pdf.
  * Sanchez et al. (a) Daniel L. Sanchez, Nils Johnson, Sean T. McCoy, Peter A. Turner, and Katharine J. Mach.  Near-term deployment of carbon capture and sequestration from biorefineries in the united states.  115(19):4875–4880, a.  ISSN 0027-8424, 1091-6490.  doi: 10.1073/pnas.1719695115.  URL https://www.pnas.org/content/115/19/4875.  Publisher: National Academy of Sciences Section: Physical Sciences.
  * (3) Kevin Anderson and Glen Peters.  The trouble with negative emissions.  354(6309):182–183.  ISSN 0036-8075, 1095-9203.  doi: 10.1126/science.aah4567.  URL https://science.sciencemag.org/content/354/6309/182.  Publisher: American Association for the Advancement of Science Section: Perspective.
  * (4) David T Kearns.  Waste-to-energy with CCS: A pathway to carbon-negative power generation.  page 11.
  * (5) Kenneth Möllersten, Jinyue Yan, and Jose R. Moreira.  Potential market niches for biomass energy with CO2 capture and storage—opportunities for energy supply with negative CO2 emissions.  25(3):273–285.  ISSN 0961-9534.  doi: 10.1016/S0961-9534(03)00013-8.  URL http://www.sciencedirect.com/science/article/pii/S0961953403000138.
  * (6) Rob Bellamy and Oliver Geden.  Govern CO 2 removal from the ground up.  12(11):874–876.  ISSN 1752-0908.  doi: 10.1038/s41561-019-0475-7.  URL https://www.nature.com/articles/s41561-019-0475-7.  Number: 11 Publisher: Nature Publishing Group.
  * (7) Gregory F. Nemet, Max W. Callaghan, Felix Creutzig, Sabine Fuss, Jens Hartmann, Jérôme Hilaire, William F. Lamb, Jan C. Minx, Sophia Rogers, and Pete Smith.  Negative emissions—part 3: Innovation and upscaling.  13(6):063003.  ISSN 1748-9326.  doi: 10.1088/1748-9326/aabff4.  URL https://iopscience.iop.org/article/10.1088/1748-9326/aabff4/meta.  Publisher: IOP Publishing.
  * (8) Hanna Marie Breunig, Tyler Huntington, Ling Jin, Alastair Robinson, and Corinne Donahue Scown.  Temporal and geographic drivers of biomass residues in california.  139:287–297.  ISSN 0921-3449.  doi: 10.1016/j.resconrec.2018.08.022.  URL http://www.sciencedirect.com/science/article/pii/S0921344918303148.
  * (9) Sarah E. Baker, Joshsuah K. Stolaroff, George Peridas, Simon H. Pang, Hannah M. Goldstein, Felicia R. Lucci, Wenqin Li, Eric W. Slessarev, Jennifer Pett-Ridge, Frederick J. Ryerson, Jeff L. Wagoner, Whitney Kirkendall, Roger D. Aines, Daniel L. Sanchez, Bodie Cabiyo, Joffre Baker, Sean McCoy, Sam Uden, Ron Runnebaum, Jennifer Wilcox, and Colin McCormick.  Getting to neutral: Options for negative emissions in california.  URL https://www-gs.llnl.gov/content/assets/docs/energy/Getting_to_Neutral.pdf.
  * (10) Julie Witcover.  Status review of california’s low carbon fuel standard, 2011–2018 q1 september 2018 issue.  URL https://escholarship.org/uc/item/445815cd.
  * (11) California Air Resources Board.  Low carbon fuel standard amendments.  URL https://ww2.arb.ca.gov/rulemaking/2019/lcfs2019.
  * (12) Bill text - SB-1383 short-lived climate pollutants: methane emissions: dairy and livestock: organic waste: landfills.  URL https://leginfo.legislature.ca.gov/faces/billNavClient.xhtml?bill_id=201520160SB1383.
  * US EPA (a) OAR US EPA.  AgSTAR: Biogas recovery in the agriculture sector, a.  URL https://www.epa.gov/agstar.  Library Catalog: www.epa.gov.
  * (14) Argonne National Laboratory.  Renewable natural gas database.  URL https://www.anl.gov/es/reference/renewable-natural-gas-database.  Library Catalog: www.anl.gov.
  * (15) CalRecycle.  California anaerobic digestion projects accepting organics from the municipal solid waste stream.
  * US EPA (b) OAR US EPA.  Landfill methane outreach program (LMOP), b.  URL https://www.epa.gov/lmop.  Library Catalog: www.epa.gov.
  * (17) Matthew D Ong, Robert B Williams, and Stephen R Kaffka.  Comparative assessment of technology options for biogas clean-up.  page 161.
  * (18) Qie Sun, Hailong Li, Jinying Yan, Longcheng Liu, Zhixin Yu, and Xinhai Yu.  Selection of appropriate biogas upgrading technology-a review of biogas cleaning, upgrading and utilisation.  51:521–532.  ISSN 1364-0321.  doi: 10.1016/j.rser.2015.06.029.  URL http://www.sciencedirect.com/science/article/pii/S1364032115006012.
  * (19) Elisa Esposito, Loredana Dellamuzia, Ugo Moretti, Alessio Fuoco, Lidietta Giorno, and Johannes C. Jansen.  Simultaneous production of biomethane and food grade CO2 from biogas: an industrial case study.  12(1):281–289.  ISSN 1754-5706.  doi: 10.1039/C8EE02897D.  URL https://pubs.rsc.org/en/content/articlelanding/2019/ee/c8ee02897d.  Publisher: The Royal Society of Chemistry.
  * noa (a) NATCARB/ATLAS, a.  URL https://www.netl.doe.gov/coal/carbon-storage/strategic-program-support/natcarb-atlas.  Library Catalog: www.netl.doe.gov.
  * noa (b) Project OSRM, b.  URL http://project-osrm.org/.
  * (22) Nathan Parker, Robert Williams, Rosa Dominguez-Faus, and Daniel Scheitrum.  Renewable natural gas in california: An assessment of the technical and economic potential.  111:235–245.  ISSN 0301-4215.  doi: 10.1016/j.enpol.2017.09.034.  URL http://www.sciencedirect.com/science/article/pii/S0301421517305955.
  * (23) P. W. Tittmann, N. C. Parker, Q. J. Hart, and B. M. Jenkins.  A spatially explicit techno-economic model of bioenergy and biofuels production in california.  18(6):715–728.  ISSN 0966-6923.  doi: 10.1016/j.jtrangeo.2010.06.005.  URL http://www.sciencedirect.com/science/article/pii/S0966692310000864.
  * (24) Peter C. Psarras, Stephen Comello, Praveen Bains, Panunya Charoensawadpong, Stefan Reichelstein, and Jennifer Wilcox.  Carbon capture and utilization in the industrial sector.  51(19):11440–11449.  ISSN 1520-5851.  doi: 10.1021/acs.est.7b01723.
  * (25) David L. McCollum and Joan M. Ogden.  Techno-economic models for carbon dioxide compression, transport, and storage & correlations for estimating carbon dioxide density and viscosity.  URL https://escholarship.org/uc/item/1zg00532.
  * (26) Robert Trautz, Joseph Swisher, Laura Chiaramonte, Rebecca Hollis, Joshua Perron, Keith Pronske, Richard Myhre, Marian Stone, Dayanand Saini, Preston Jordan, Jeff Wagoner, and Ronald Kent.  California CO2 storage assurance facility enterprise (c2safe): Final technical report.  URL https://www.osti.gov/biblio/1452864-california-co2-storage-assurance-facility-enterprise-c2safe-final-technical-report.
  * (27) Yeqing Li, Ruihong Zhang, Guangqing Liu, Chang Chen, Yanfeng He, and Xiaoying Liu.  Comparison of methane production potential, biodegradability, and kinetics of different organic substrates.  149:565–569.  ISSN 0960-8524.  doi: 10.1016/j.biortech.2013.09.063.  URL http://www.sciencedirect.com/science/article/pii/S0960852413014958.
  * US EPA (c) OAR US EPA.  Emissions & generation resource integrated database (eGRID), c.  URL https://www.epa.gov/energy/emissions-generation-resource-integrated-database-egrid.  Library Catalog: www.epa.gov.
  * (29) Environmental Defense Fund.  Green freight math: How to calculate emissions for a truck move.  URL https://business.edf.org/insights/green-freight-math-how-to-calculate-emissions-for-a-truck-move/.  Library Catalog: business.edf.org.
  * EIA (2021) EIA.  California natural gas consumption by end use.  https://www.eia.gov/dnav/ng/ng_cons_sum_dcu_SCA_a.htm, 2021.
  * N-79-20 (2020) California Executive Order N-79-20, 2020.
  * (32) Erin Burns and Rory Jacobson.  Enhancing and expanding the 45q tax credit for direct air capture.
  * McQueen et al. (2020) Noah McQueen, Peter Psarras, Hélène Pilorgé, Simona Liguori, Jiajun He, Mengyao Yuan, Caleb M Woodall, Kourosh Kian, Lara Pierpoint, Jacob Jurewicz, et al.  Cost analysis of direct air capture and sequestration coupled to low-carbon thermal energy in the united states.  _Environmental science & technology_, 54(12):7542–7551, 2020.
  * Sanchez et al. (b) Daniel L. Sanchez, Teal Zimring, Catherine Mater, Katie Harrell, Stephen Kelley, Lech Muszynski, Ben Edwards, Samantha Smith, Kyle Monper, AnnaClaire Marley, and Max Russer.  Literature review and evaluation of research gaps to support wood products innovation.  b.
  * (35) Amber Mahone, Jenya Kahn-Lang, Vivian Li, Nancy Ryan, Zachary Subin, Douglas Allen, Gerrit De Moor, and Snuller Price.  Deep decarbonizaiton in a high renewables future.  URL https://www.ethree.com/wp-content/uploads/2018/06/Deep_Decarbonization_in_a_High_Renewables_Future_CEC-500-2018-012-1.pdf.
  * (36) Gas Technology Institue.  Low carbon renewable natural gas (RNG) from wood wastes.  URL https://www.gti.energy/wp-content/uploads/2019/02/Low-Carbon-Renewable-Natural-Gas-RNG-from-Wood-Wastes-Final-Report-Feb2019.pdf.
  * (37) Emily Grubert.  At scale, renewable natural gas systems could be climate intensive: The influence of methane feedstock and leakage rates.  ISSN 1748-9326.  doi: 10.1088/1748-9326/ab9335.  URL http://iopscience.iop.org/10.1088/1748-9326/ab9335.


# Achievable Rates and Algorithms for Group Testing with Runlength Constraints

Stefano Della Fiore  Deparment of Information Engineering
University of Brescia
Brescia (BS), Italy
<EMAIL_ADDRESS>Marco Dalai  Deparment of Information Engineering
University of Brescia
Brescia (BS), Italy
<EMAIL_ADDRESS>Ugo Vaccaro  Department of Informatics
University of Salerno
Fisciano (SA), Italy
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study bounds on the minimum length of $(k,n,d)$-superimposed
codes introduced by Agarwal et al. [1], in the context of Non-Adaptive Group
Testing algorithms with runlength constraints. A $(k,n,d)$-superimposed code
of length $t$ is a $t\times n$ binary matrix such that any two 1’s in each
column are separated by a run of at least $d$ 0’s, and such that for any
column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where
$\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. Agarwal et
al. proved the existence of such codes with
$t=\Theta(dk\log(n/k)+k^{2}\log(n/k))$. Here we investigate more in detail the
coefficients in front of these two main terms as well as the role of lower
order terms. We show that improvements can be obtained over the construction
in [1] by using different constructions and by an appropriate exploitation of
the Lovász Local Lemma in this context. Our findings also suggest $O(n^{k})$
randomized Las Vegas algorithms for the construction of such codes. We also
extend our results to Two-Stage Group Testing algorithms with runlength
constraints.

###### Index Terms:

Lovász Local Lemma, superimposed codes, runlength-constrained codes.

##  I Introduction

Group Testing refers to the scenario in which one has a population $I$ of
individuals, and an unknown subset $P$ of $I$, commonly referred to as
“positives”. The goal is to determine the unknown elements of $P$ by
performing tests on arbitrary subsets $A$ of $I$ (called pools), and the
outcome of the test is assumed to return the value 1 (positive) if $A$
contains at least one element of the unknown set $P$, the value 0 (negative),
otherwise. The problem was first introduced by Dorfman [5] during WWII, in the
context of mass blood testing. Since then, Group Testing techniques have found
applications in a large variety of areas, ranging from DNA sequencing to
quality control, data security to network analysis, and much more. We refer
the reader to the excellent monographs [6, 9] for an account of the vast
literature on the subject.

Group Testing procedures can be adaptive or non-adaptive. In adaptive Group
Testing, the tests are performed sequentially, and the content of the pool
tested at the generic step $i$ might depend on the previous $i-1$ test
outcomes. Conversely, in non-adaptive Group Testing all pools are a-priori
set, and tests are carried out in parallel. Non-adaptive Group Testing (NAGT)
schemes typically require more tests to discover the positives, but they are
faster since tests can be performed in parallel. To combine the advantages of
both techniques, while mitigating their limitations, it is sometimes
preferable to implement a hybrid approach, where a first screening is
performed via a NAGT algorithm, followed by a simple one-by-one testing of the
members that are identified in the first stage as potentially positives. This
latter approach is usually called Two-Stage Group Testing [4].

In NAGT, the algorithm to determine the positives is usually represented by
means of a $t\times n$ binary matrix $M$, where each row of $M$ represents a
test while each column is associated to a distinct member of the population
$I=\\{1,2,\ldots,n\\}$. More precisely, we have $M_{ij}=1$ if and only if the
member $j\in I$ belongs to the $i$-th test. In general, one assumes a known
upper bound $k$ on the cardinality of the unknown set of positives $P$. Having
said that, the property one usually requires for $M$ to represent a correct
(and efficiently decodable) NAGT is the following [6]: for any $k$-tuple of
the $n$ columns of $M$ we demand that for any column $\mathbf{c}$ of the given
$k$-tuple, there exists a row ${i\in\\{1,\ldots,t\\}}$ such that $\mathbf{c}$
has symbol $1$ in row $i$ and all the remaining $k-1$ columns of the $k$-tuple
have a $0$ in the same row $i$. This condition renders matrices $M$ with such
a property equivalent to the well known superimposed codes introduced in the
seminal paper by Kautz and Singleton [10] and, independently, by Erdös et al.
in [7].

Motivated by applications in topological DNA-based data storage, the authors
of [1] introduced an interesting new variant of NAGT, in which the associated
test matrix $M$ has to satisfy additional constraints, in order to comply with
the biological constraints of the problem they want to solve. Informally, one
of the main problems studied in [1] is to show the existence of a superimposed
code $M$ with a ”small” number $t$ of rows and satisfying the following
additional property: any two 1’s in each column are separated by a run of at
least $d$ 0’s. We refer the reader to [1] for the rationale behind this run-
length constraint. The main achievability result obtained in [1] says that
codes with these properties exist for $t=\Theta(dk\log(n/k)+k^{2}\log(n/k))$.

Our results. We study the achievable coefficients in front of the
$dk\log(n/k)$ and $k^{2}\log(n/k)$ terms and on lower order terms in $k$,
whose values are of importance as they determine the achievable rates of such
codes for fixed values of $d$ and $k$. We show that better results than those
derived in [1] can be obtained using different random coding constructions
which also admit simpler analyses. Also, we show that improved results can be
obtained by an appropriate use of the Lovász Local Lemma (see, e.g., [2]). By
exploiting the celebrated result by Moser and Tardos [12], this directly
implies a $O(n^{k})$ randomized Las Vegas algorithm to construct such codes.
In the final part of this paper, we also extend our results to Two Stages
Group Testing algorithms.

##  II New Upper Bounds

Throughout the paper, the logarithms without subscripts are in base two, and
we denote with $\ln(\cdot)$ the natural logarithm. For notation convenience we
denote with $[a,b]$ the set ${\\{a,a+1,\ldots,b\\}}$.

######  Definition II.1.

[1] Let $k$, $n$, $d$ be positive integers, $k\leq n$. A
$(k,n,d)$-_superimposed_ code is a $t\times n$ binary matrix $M$ such that any
two 1’s in each column of $M$ are separated by a run of at least $d$ 0’s, and
for any $k$-tuple of the columns of $M$ we have that for any column
$\mathbf{c}$ of the given $k$-tuple, there exists a row ${i\in[1,t]}$ such
that $\mathbf{c}$ has symbol $1$ in row $i$ and all the remaining $k-1$
columns of the $k$-tuple are equal to $0$. The number of rows $t$ of $M$ is
called the length of the $(k,n,d)$-superimposed code.

######  Definition II.2.

A $(k,n,d,w)$-_superimposed_ code is a $(k,n,d)$-superimposed with the
additional constraint that each column has weight $w$ (number of ones).

First, we need the following enumerative lemma.

######  Lemma II.3.

Let $S\subseteq\\{0,1\\}^{t}$ be the set of all distinct binary vectors of
length $t$ such that each vector has Hamming weight $w\geq 1$ and any two 1’s
in each vector are separated by a run of at least $d$ 0’s. If $t\geq(w-1)d+w$,
then

$|S|=\binom{t-(w-1)d}{w}\,.$

###### Proof.

Let $A$ be the set of all distinct binary vectors of length $t-(w-1)d$ and
weight $w$. One can see that $|S|=|A|$ since each element of $S$ can be
obtained from an element $a\in A$ by adding between each pair of consecutive
ones in $a$ exactly $d$ 0’s. Conversely, each element of $A$ can be obtained
from an element $s\in S$ by removing between each pair of consecutive ones in
$s$ exactly $d$ 0’s. ∎

We also need the following technical lemma and an easy corollary, which have
been proved in [8]. We report here the proofs for the reader’s convenience.

######  Lemma II.4.

Let $a,b,c$ be positive integers such that $c\leq a\leq b$. We have that

$\frac{a}{b}\cdot\frac{a-c}{b-c}\leq\left(\frac{a-\frac{c}{2}}{b-\frac{c}{2}}\right)^{2}\,.$

###### Proof.

Clearly $a(a-c)c^{2}\leq b(b-c)c^{2}$. Then adding the quantity
$4ab(a-c)(b-c)$ to both members implies that $a(a-c)(2b-c)^{2}\leq
b(b-c)(2a-c)^{2}$. Therefore Lemma II.4 follows. ∎

######  Corollary II.5.

Let $a,b,c$ be positive integers such that $c\leq a\leq b$. We have that

$\frac{\binom{a}{c}}{\binom{b}{c}}\leq\left(\frac{a-\frac{c-1}{2}}{b-\frac{c-1}{2}}\right)^{c}\,.$
(1)

###### Proof.

Expanding the LHS of (1) we get

$\frac{\binom{a}{c}}{\binom{b}{c}}=\frac{a}{b}\cdot\frac{a-1}{b-1}\cdots\frac{a-c+1}{b-c+1}\,.$
(2)

Let us group the terms in (2) into pairs as follows

$\frac{a-i}{b-i}\cdot\frac{a-(c-i-1)}{b-(c-i-1)}\text{ for
}i=0,\ldots,\left\lceil\frac{c-1}{2}\right\rceil-1\,.$ (3)

If $c$ is odd then we leave alone the term
$(a-\frac{c-1}{2})/(b-\frac{c-1}{2})$. By Lemma II.4, each term in (3) can be
upper bounded by

$\frac{a-i}{b-i}\cdot\frac{a-(c-i-1)}{b-(c-i-1)}\leq\left(\frac{a-\frac{c-1}{2}}{b-\frac{c-1}{2}}\right)^{2}\,.$

Hence Corollary II.5 follows. ∎

The main tool to prove Theorem II.7 is the Lovász Local Lemma for the
symmetric case. We state here the lemma.

######  Lemma II.6.

[2] Let $E_{1},E_{2},\ldots,E_{m}$ be events in an arbitrary probability
space. Suppose that each event $E_{i}$ is mutually independent of a set of all
other events $E_{j}$ but at most $d$, and that $\Pr(E_{i})\leq p$ for all
$1\leq i\leq m$. If

$edp\leq 1$

then $\Pr(\cap_{i=1}^{m}\overline{E}_{i})>0$.

Now, we are ready to state our main result.

######  Theorem II.7.

There exists a $(k,n,d,w)$-superimposed code of length $t$, where $t$ is the
minimum integer such that the following inequality holds

$ek\left[\binom{n}{k}-\binom{n-k+1}{k}\right]\left(\frac{w(k-1)-\frac{w-1}{2}}{t-(w-1)d-\frac{w-1}{2}}\right)^{w}\leq
1.$ (4)

###### Proof.

Let $M$ be a $t\times n$ binary matrix, where each column $\mathbf{c}$ is
picked uniformly at random between the set of all distinct binary vectors of
length $t$ such that each column has weight $w$ and any two 1’s in each column
of $M$ are separated by a run of at least $d$ 0’s. Therefore by Lemma II.3 we
have that

$\Pr(\mathbf{c})=\binom{t-(w-1)d}{w}^{-1}\,.$

For a given index $i\in[1,n]$ and a set of column-indices $B$, $|B|=k-1$,
$i\not\in B$, let $E_{i,B}$ be the event such that for every row in which
$\mathbf{c}_{i}$ (the $i$-th column) has $1$, there exists an index $j\in B$
such that $\mathbf{c}_{j}$ has $1$ in that same row. We can write this event
in terms of supports as
$\operatorname{Supp}(\mathbf{c}_{i})\subseteq\operatorname{Supp}(\mathbf{c}_{B})$.
There are $n\binom{n-1}{k-1}$ such events. We can express the probability of
such an event as follows

$\displaystyle\Pr(E_{i,B})=$
$\displaystyle\sum_{c^{\prime}=(c^{\prime}_{1},\ldots,c^{\prime}_{k-1})}\Pr(\mathbf{c}_{B}=c^{\prime})\cdot$
$\displaystyle\Pr(\operatorname{Supp}(\mathbf{c}_{i})\subseteq\operatorname{Supp}(\mathbf{c}_{B})|\mathbf{c}_{B}=c^{\prime}),$
(5)

where we have denoted with $\mathbf{c}_{B}$ the vector
$(\mathbf{c}_{j_{1}},\ldots,\mathbf{c}_{j_{k-1}})$ in which
$j_{1},\ldots,j_{k-1}$ are the elements of $B$. The sum in (II) is over all
the possible configurations of $k-1$ vectors of length $t$, weight $w$ and the
distance between ones in each column is at least $d$. Then, we can upper bound
(II) by the maximum of
$\Pr(\operatorname{Supp}(\mathbf{c}_{i})\subseteq\operatorname{Supp}(\mathbf{c}_{B})|\mathbf{c}_{B}=c^{\prime})$
over all $k-1$ vectors $c^{\prime}=(c^{\prime}_{1},\ldots,c^{\prime}_{k-1})$.
Therefore, we can consider the worst-case scenario where the $k-1$ columns of
$M$ with indices in $B$ maximize this probability. It can be seen that the
maximum is achieved when the $w(k-1)$ ones of the $k-1$ columns indexed by $B$
are placed in $w(k-1)$ different rows. Hence,

$\Pr(E_{i,B})\leq\frac{\binom{w(k-1)}{w}}{\binom{t-(w-1)d}{w}}\,.$ (6)

Using Corollary II.5 we upper bound (6) as follows

$\Pr(E_{i,B})\leq\left(\frac{w(k-1)-\frac{w-1}{2}}{t-(w-1)d-\frac{w-1}{2}}\right)^{w}\,.$
(7)

Proceeding as in [8], it can be proved that an arbitrary event $E_{i,A}$ is
mutually independent from all the events $E_{j,C}$, where
$C\subseteq[1,n]\setminus(A\cup\\{i\\})$ and $j\not\in C$. Since the number of
events $E_{j,C}$ is equal to

$\binom{n-k}{k-1}(n-k+1)=k\binom{n-k+1}{k}\,,$

each event $E_{i,A}$ is dependent of at most

$f=k\left[\binom{n}{k}-\binom{n-k+1}{k}\right]$ (8)

other events. If the probability that none of the events $E_{i,A}$ occurs is
strictly positive then there exists a matrix $M$ that is a
$(k,n,d,w)$-superimposed code of length $t$. Therefore, using Lemma II.6 and
taking $p$ equal to the RHS of (7) and $f$ as defined in equation (8), Theorem
II.7 follows. ∎

######  Remark II.8.

We note that in Theorem II.7 we could use the union bound instead of the Local
Lemma. Since the total number of events is $n\binom{n-1}{k-1}$, we have that
there exists a $(k,n,d,w)$-superimposed code of length $t$, provided that

$n\binom{n-1}{k-1}\left(\frac{w(k-1)-\frac{w-1}{2}}{t-(w-1)d-\frac{w-1}{2}}\right)^{w}<1\,.$
(9)

In [1] the authors proved that a $(k,n,d,w)$-superimposed code of length $t$
exists, provided that

$n\binom{n-1}{k-1}\left(\frac{w(k-1)}{t-(2d+1)(w-1)}\right)^{w}<1\,.$ (10)

It is clear that our bound given in Remark II.8 is better than the bound given
in (10) since

$\frac{w(k-1)-\frac{w-1}{2}}{t-(w-1)d-\frac{w-1}{2}}\leq\frac{w(k-1)}{t-(2d+1)(w-1)}$

for all positive integers $w,k,d$.

If we compare the bounds of Theorem II.7 and Remark II.8 then it has been
proved in [8] that

$ek\left[\binom{n}{k}-\binom{n-k+1}{k}\right]\leq n\binom{n-1}{k-1}$ (11)

for all $k\leq 0.667\sqrt{n}$. Therefore when $k$ is much smaller than $n$
(which is indeed the case in circumstances of interest), the Local Lemma
performs better than the union bound. It is important to note that a
conjecture of Erdős, Frankl and Füredi [7] says that for $k\geq\sqrt{n}$
optimal superimposed codes have length equal to $n$. The current best known
result has been proved in [13] which states that if $k\geq 1.157\sqrt{n}$ then
the minimum length of superimposed codes is equal to $n$.

######  Corollary II.9.

There exists a $(k,n,d,w)$-superimposed code of length $t$, where

$t\leq\Bigg{\lceil}(w-1)d+\frac{w-1}{2}+\left(w(k-1)-\frac{w-1}{2}\right)\cdot\\\
\left(\min\left\\{n\binom{n-1}{k-1},ek\left[\binom{n}{k}-\binom{n-k+1}{k}\right]\right\\}\right)^{\frac{1}{w}}\Bigg{\rceil}\,.$
(12)

###### Proof.

It easily follows rearranging the terms in equation (4) and in equation (9). ∎

######  Corollary II.10.

There exists a $(k,n,d)$-superimposed code of length $t$ with $k\leq n/e$,
where

$t\leq\ln 2\cdot dk\log(n/k)+e^{2}\cdot k^{2}\log(n/k)\\\
-\frac{\left(3e^{2}-\ln 2\right)}{2}k\log(n/k)-d+O(1)\,.$

###### Proof.

Substitute $w=k\ln(n/k)$ in (12) and upper bound

$\min\left\\{n\binom{n-1}{k-1},ek\left[\binom{n}{k}-\binom{n-k+1}{k}\right]\right\\}<k\left(\frac{en}{k}\right)^{k}\,.$

Therefore we obtain

$t\leq d\left(k\ln(n/k)-1\right)+\frac{k}{2}\ln(n/k)\\\
+e\cdot(ke^{k})^{\frac{1}{k\ln(n/k)}}k\left(k-\frac{3}{2}\right)\ln(n/k)+O(1).$
(13)

Hence Corollary II.10 follows since $n\geq ek$ and $k^{1/k}\leq\frac{1}{\ln
2}$ for every integer $k\geq 1$. ∎

We note that in the explicit bound given in Corollary II.10 the leading
coefficient of the term $k\log(n/k)$ can be improved, for $k\leq
0.667\sqrt{n}$, by using a better estimation of the minimum in equation (12)
that comes from the use of the Local Lemma.

By exploiting the celebrated result by Moser and Tardos [12], this directly
implies a $O(n^{k})$ randomized Las Vegas algorithm to construct the codes of
Corollary II.10

From the inequality (10) we can derive an explicit upper bound on the length
of the codes whose existence was showed in [1] when $w=k\ln(n/k)$ by upper
bounding $n\binom{n-1}{k-1}$ with $k\left(\frac{en}{k}\right)^{k}$. We report
here the obtained result.

######  Theorem II.11.

[1] There exists a $(k,n,d)$-superimposed code of length $t$, where

$t\leq 2d\left(k\ln(n/k)-1\right)+k\ln(n/k)\\\
+e\cdot(ke^{k})^{\frac{1}{k\ln(n/k)}}k(k-1)\ln(n/k)+O(1).$

It is clear that our result given in equation (13) improves the one of Theorem
II.11.

######  Remark II.12.

We note that it was proved in [1] that every $(k,n,d)$-superimposed code of
length $t$ must satisfy

$t\geq\min\left\\{n,1+(k-1)(d+1)\right\\}\,.$

This implies that if $k\geq\frac{n-1}{d+1}+1$ then $t=n$, so we cannot
construct a $(k,n,d)$-superimposed code of length $t$ that is better than the
identity matrix of size $n\times n$.

By Remark II.12, it is clear that the constraint $k\leq n/e$ in Corollary
II.10 is reasonable since $1+(k-1)(d+1)\geq ek$ for every $k,d\geq 2$.

We also note that a simple generalization of the method given by Cheng et al.
in [3] provide the following result.

######  Theorem II.13.

There exists a $(k,n,d)$-superimposed code of length $t$,
$t\leq\frac{1}{B_{k}}\left(k\log(n/k)+\log(ke^{k})\right)$, where

$\displaystyle B_{k}=\max_{q\geq 2}B_{k,q}\,,$ (14) $\displaystyle
B_{k,q}=\frac{-\log\left[1-\left(1-\frac{1}{q}\right)^{k-1}\right]}{q+d}\,.$

For $k\to\infty$, the point $q$ that maximize (14) is linear in $k$.

The proof of Theorem II.13 is similar to the one in [3], we only need to
ensure that when we construct a binary matrix $M$ starting from a random
$q$-ary matrix each column $\bf c$ of $M$ has a run of at least $d$ $0$’s
between any two $1$’s. This can be done by mapping each $q$-ary symbol into a
binary vector of length $q+d$ where the last $d$ elements are fixed to $0$.

If we lower bound $B_{k}$ with $B_{k,q}$ for the choice ${q=\frac{1}{\ln
2}(k-1)}$ then, for $k$ sufficiently large, Theorem II.13 gives the following
explicit bound on the minimum length $t$ of $(k,n,d)$-superimposed codes

$t\leq dk\log(n/k)+\frac{1}{\ln 2}\cdot k(k-1)\log(n/k)\\\ +\left(\frac{1}{\ln
2}(k-1)+d\right)\log\left(ke^{k}\right)+O(1).$ (15)

One can see that this bound already improves, for $k$ sufficiently large, the
one given in Theorem II.11 but not the one obtained in Corollary II.10 for
$k<d$.

##  III Selectors

Selectors were introduced in [4] and they can be seen as a generalization of
superimposed codes. Like superimposed codes, selectors find applications in
many circumstances, like Group Testing [4], efficient conflict resolution in
the transmission model of [11], etc.. In this section, we introduce selectors
in which the weight of each column is equal to some fixed value $w$ and where
any two 1’s in each column of $M$ are separated by a run of at least $d$ 0’s,
so that they can be applied to the scenario of [1]. Successively, we will show
that selectors can be used to construct efficient two-stage procedure for
Group Testing with runlength constraints, that require a much smaller number
of tests, with respect to the NAGT considered in [1] and in the previous
section of the present paper. Let us start by giving some definitions.

######  Definition III.1.

Let $k$, $n$, $d$, $p$ be positive integers, $1\leq p\leq k\leq n$. A
$(k,n,d,p)$-_selector_ is a $t\times n$ binary matrix $M$ such that any two
1’s in each column of $M$ are separated by a run of at least $d$ 0’s, and for
any $k$-tuple of the columns of $M$ we have that at least $p$ rows of the
identity matrix of size $k\times k$ are contained in that $k$-tuple of
columns. The number of rows $t$ of $M$ is called the length of the
$(k,n,d,p)$-selector.

One can see that for $p=k$ we get the definition of $(k,n,d)$-superimposed
codes studied in Section II.

######  Definition III.2.

A $(k,n,d,p,w)$-_selector_ is a $(k,n,d,p)$-selector with the additional
constraint that each column has weight $w$.

It can be seen (see [8, Lemma 2]) that Definition III.1 is equivalent to
requiring that for any $k$-tuple of columns of a $(k,n,d,p)$-selector and any
$k-p+1$ columns among the selected $k$-tuple, there exists a row of the
identity matrix of size $k\times k$ where the $1$ is contained in one of the
$k-p+1$ columns. Therefore, thanks to this equivalence, we can generalize the
proof of Theorem II.7 to obtain the following.

######  Theorem III.3.

There exists a $(k,n,d,p,w)$-selector of length $t$, where $t$ is the minimum
integer such that the following inequality holds

$e\binom{k}{p-1}\left[\binom{n}{k}-\binom{n-k}{k}\right]\cdot\\\
\left(\frac{w(k-1)-\frac{w-1}{2}}{t-(w-1)d-\frac{w-1}{2}}\right)^{w(k-p+1)}\leq
1.$ (16)

###### Proof.

Let $M$ be a $t\times n$ binary matrix, where each column $\mathbf{c}$ is
picked uniformly at random between the set of all distinct binary vectors of
length $t$ such that each column has weight $w$ and with distance between ones
in each column at least $d$. As in Theorem II.7, by Lemma II.3 we have that

$\Pr(\mathbf{c})=\binom{t-(w-1)d}{w}^{-1}\,.$

For a given pair of sets $B_{1}$, $B_{2}\subseteq[1,n]$ where $|B_{1}|=k-p+1$,
$|B_{2}|=p-1$ and $B_{1}\cap B_{2}=\emptyset$, let $E_{B_{1},B_{2}}$ be the
event such that for each column $\mathbf{c}_{i}$ with $i\in B_{1}$ and every
row $r$ where $\mathbf{c}_{i}(r)=1$ there exists an index $j\in(B_{1}\cup
B_{2}\setminus\\{i\\})$ such that $\mathbf{c}_{j}$ has $1$ in that same row
$r$. There are $\binom{k}{p-1}\binom{n}{k}$ such events. Then, by the same
argument used in the proof of Theorem II.7 we can easily upper bound the
probability of such events as follows

$\Pr(E_{B_{1},B_{2}})\leq\left(\frac{\binom{w(k-1)}{w}}{\binom{t-(w-1)d}{w}}\right)^{k-p+1}\,.$
(17)

Using Corollary II.5 we upper bound (17) as follows

$\Pr(E_{B_{1},B_{2}})\leq\left(\frac{w(k-1)-\frac{w-1}{2}}{t-(w-1)d-\frac{w-1}{2}}\right)^{w(k-p+1)}\,.$
(18)

Let us fix an arbitrary event $E_{A_{1},A_{2}}$ then it is easy to see that it
is mutually independent from all the events
$E_{A^{\prime}_{1},A^{\prime}_{2}}$ such that
$A^{\prime}_{1}\subseteq[1,n]\setminus(A_{1}\cup A_{2})$,
$A^{\prime}_{2}\subseteq[1,n]\setminus(A_{1}\cup A_{2}\cup A^{\prime}_{1})$.
The number of events $E_{A^{\prime}_{1},A^{\prime}_{2}}$ is equal to
$\binom{k}{p-1}\binom{n-k}{k}$. Therefore each event $E_{A_{1},A_{2}}$ is
dependent of at most

$f=\binom{k}{p-1}\left[\binom{n}{k}-\binom{n-k}{k}\right]$ (19)

other events. If the probability that none of the events $E_{A_{1},A_{2}}$
occurs is strictly positive then there exists a matrix $M$ that is a
$(k,n,d,p,w)$-selector of length $t$. Using Lemma II.6 and taking $p$ equal to
the RHS of (18) and $f$ as defined in equation (19), Theorem III.3 follows. ∎

######  Corollary III.4.

There exists a $(k,n,d,p,w)$-selector of length $t$, where

$t\leq\Bigg{\lceil}(w-1)d+\frac{w-1}{2}+\left(w(k-1)-\frac{w-1}{2}\right)\cdot\\\
\left(e\binom{k}{p-1}\left[\binom{n}{k}-\binom{n-k}{k}\right]\right)^{\frac{1}{w(k-p+1)}}\Bigg{\rceil}\,.$
(20)

###### Proof.

It follows rearranging the terms in equation (16). ∎

Again, by exploiting the result by Moser and Tardos [12], we get a $O(n^{k})$
randomized Las Vegas algorithm to construct the codes of Corollary III.4

Thanks to Corollary III.4 we obtain the following upper bound on the minimum
length of $(k,n,d,p)$-selectors.

######  Corollary III.5.

There exists a $(k,n,d,p)$-selector of length $t$ with $k\leq n/e$, where

$t\leq\ln 2\cdot\frac{dk}{k-p+1}\log(n/k)\\\ +\ln 2\cdot
e^{3+\frac{1}{e}}\frac{k^{2}}{k-p+1}\log(n/k)+O(k\log(n/k))\,.$

###### Proof.

Substituting $w=\frac{k}{k-p+1}\ln(n/k)$ in (20) and using the well-known
inequality $\binom{m}{s}\leq\left(\frac{em}{s}\right)^{s}$, we get

$t\leq\frac{dk}{k-p+1}\ln(n/k)\\\
+e\left[e^{1+\frac{p}{k}}\left(\frac{k}{p-1}\right)^{\frac{p-1}{k}}\right]^{\frac{1}{\ln(n/k)}}\frac{k^{2}}{k-p+1}\ln(n/k)\\\
+O(k\ln(n/k))\,.$

Hence Corollary III.5 follows since $p\leq k$, $n\geq ek$ and since the
function $x^{1/x}$ takes its maximum at $x=e$. ∎

###  III-A Application of $(k,n,d,p)$-selectors to two-stage Group Testing
with runlength constraints

We need the following result, whose proof for ”classical” selectors (that is,
for selectors without the runlength constraint studied in this paper) is
implicit in the discussion before Theorem 3 of [4]. It is trivial to see that
the proof carries out also in the present scenario.

######  Lemma III.6.

Let $M$ be a $(k,n,d,p)$-selector with $t$ rows, and let ${\bf f}$ be the
$t\times 1$ columns vector obtained by the bitwise OR of at most $q$, $q\leq
p-1$, columns ${\mathbf{c}_{i_{1}}},\ldots,{\mathbf{c}_{i_{q}}}$ of $M$. Then,
apart from ${\mathbf{c}_{i_{1}}},\ldots,{\mathbf{c}_{i_{q}}}$, there are at
most other $k-q-1$ columns of $M$ whose 1’s are in a subset of the positions
in which the vector ${\bf f}$ also has 1’s.

Now we proceed as follows. Let $k$ be an upper bound on the number of possible
positives in the Group Testing problem. We perform all the tests corresponding
to the rows of a $(2k,n,d,k+1)$-selector $M$, as explained in the
introduction. More precisely, the generic $i$-th pool $T_{i}$, for
$i=1,\ldots,t$, contains all elements $j\in[1,n]$ for which $M_{ij}=1$. After
having performed (in parallel) all tests on pools $T_{1},\ldots,T_{t}$, we get
a ”sindrome” vector ${\bf f}$ (of dimension $t\times 1$) equal to the bitwise
OR of the (at most) $k$ columns that correspond to the unknown positive
elements. The number of columns of $M$ that are ”covered” by ${\bf f}$ (that
is, that have their 1’s in a subset of the positions in which the vector ${\bf
f}$ also has 1’s) is upper bounded by $2k$ (by Lemma III.6). In other words,
there are at most $s\leq 2k$ potentially positive elements, and the true
positive are among them. Hence, one can test individually those $s$ elements
to discover the true positives. Altogether, we have used $t+2k$ tests.

By using Corollary III.5 to estimate $t$, we get that we can discover all the
positive elements by performing a number of tests upper bounded by a quantity
that is

$2d\ln(n/k)+O(k\ln(n/k)).$ (21)

The bound (21) shows that our two-stage Group Testing algorithm outperforms
both the NAGT algorithm presented in [1] and also our improved one given in
the previous section of the present paper. It is interesting to notice that
the bound (21) is information-theoretic optimal, for $d=O(k)$, and that this
optimality can be achieved by introducing the least amount of adaptivity in
the testing algorithm.

## References

  * [1] A. Agarwal, O. Milenkovic and S. Pattabiraman and J. Ribeiro, Group Testing with Runlength Constraints for Topological Molecular Storage, 2020 IEEE International Symposium on Information Theory, 132-137.
  * [2] N. Alon and J. Spencer, The Probabilistic Method, Wiley, 2008.
  * [3] Y. Cheng, D.-Z. Du, G. Lin, On the upper bounds of the minimum number of rows of disjunct matrices, Optim. Lett. 3 (2009), 297–302.
  * [4] A. De Bonis, L. Gasieniec and U. Vaccaro, Optimal Two-Stage Algorithms for Group Testing Problems, SIAM Journal on Computing, vol. 34, no.5, 1253–1270, 2005.
  * [5] R. Dorfman, The Detection of Defective Members of Large Populations, Ann. Math. Statist. 14(4): 436-440 (December, 1943).
  * [6] D.-Z. Du and F.K. Hwang, Pooling Designs And Nonadaptive Group Testing: Important Tools For Dna Sequencing, World Scientific, 2006.
  * [7] P. Erdös, P. Frankl, Z. Füredi, Families of finite sets in which no set is covered by the union of $r$ others, Israel J. Math. 51, 79–89 (1985).

  * [8] L. Gargano, A. A. Rescigno and U. Vaccaro, Low-weight superimposed codes and related combinatorial structures: Bounds and applications, Theoretical Computer Science 806 (2020), 655–672.
  * [9] O. Johnson, J. Scarlett and M. Aldridge, Group Testing: An Information Theory Perspective, Now Publishers 2019.
  * [10] W. Kautz and R. Singleton, Nonrandom binary superimposed codes, IEEE Transactions on Information Theory, 10, (1964), 363–377.
  * [11] J. Komlos and A. Greenberg, An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels, IEEE Trans. on Information Theory, 31, Issue: 2, March 1985, 302–306.
  * [12] R.A. Moser and G. Tardos, A constructive proof of the general Lovász local lemma, Journal of the ACM, 57 (2010), 1–15.
  * [13] C. Shangguan and G. Ge, New Bounds on the Number of Tests for Disjunct Matrices, Transactions on Information Theory, vol. 62, no. 12, pp. 7518-7521, Dec. 2016.